#//////////////////////////////////////////////////////////
#// Name: Peter M. Maurer
#// Program: Sieve of Eratosthenes
#// Due: Never
#// Language: bash
#//////////////////////////////////////////////////////////

#	 define the sieve data structure
declare -a candidates[1001]  # protect against strict evaluation of booleans
#		everything is potentially prime until proven otherwise
i=0
while [ $i -lt 1001 ]
do
candidates[i]=1
i=`expr $i + 1`
done
#	 Neither 1 nor 0 is prime, so flag them off
candidates[0]=0
candidates[1]=0
#	 start the sieve with the integer 0
i=0
while [ $i -lt 1000 ]
do
#	advance to the next un-crossed out number.
#	this number must be a prime
while [ $i -lt 1000 -a ${candidates[$i]} = 0 ]
do
i=`expr $i + 1`
done
if [ $i -lt 1000 ]
then
#			// cross out all multiples of the prime, starting with 2*p.
j=2
k=`expr $i "*" $j`
while [ $k -lt 1000 ]
do
candidates[$k]=0
j=`expr $j + 1`
k=`expr $i "*" $j`
done
#			// advance to the next candidate
i=`expr $i + 1`
fi
done
#	// all uncrossed-out numbers are prime (and only those numbers)
#	// print all primes
i=0
while [ $i -lt 1000 ]
do
if [ ${candidates[$i]} != 0 ]
then
echo $i " is prime"
fi
i=`expr $i + 1`
done