#!/bin/bash
# The Sieve of Eratosthenes 
# Generate all primes less than $1

[ $# -ne 1 ] && { echo "Usage: sieve <number>"; exit 1; }

M=$(($1 / 2))
N=$(echo "scale=0;sqrt($1)/2+1" | bc)

# Skip the even numbers; P is an array of all odd numbers up to $1. 
P=( $(seq 3 2 $1) )

j=0
while test $j -le $N; do
# If P[j] is non-empty, then it's a prime. Remove its multiples...
  if test -n "${P[$j]}"; then
# ...starting from P[j]^2, as smaller multiples will have already
# been removed by an earlier iteration
    k=$(((${P[$j]} * ${P[$j]})/2 - 1))
    while test $k -le $M; do
      unset P[$k]
      let k+=${P[$j]}
    done
  fi  
  let j+=1
done  
echo 2 ${P[*]}