#!/usr/local/bin/perl
# //////////////////////////////////////////////////////////
# // Name: Peter M. Maurer
# // Program: Sieve of Eratosthenes
# // Due: Never
# // Language: Perl
# //////////////////////////////////////////////////////////

# define the sieve data structure
for ($i=0 ; $i<1000 ; $i++)
{
	# everything is potentially prime until proven otherwise
	push(@Candidates,1);
}
# 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<1000)
{
	# advance to the next un-crossed out number.
	# this number must be a prime
	while ($i<1000 && $Candidates[$i] == 0)
	{
		$i++;
	}
	# insure against running off the end of the data structure
	if ($i<1000)
	{
		# cross out all multiples of the prime, starting with 2*p.
		for ($j=2 ; $j*$i < 1000 ; $j++)
		{
			$Candidates[$j*$i] = 0;
		}
		# advance to the next candidate
		$i++;
	}
}
# all uncrossed-out numbers are prime (and only those numbers)
# print all primes
for ($i=0 ; $i<1000 ; $i++)
{
	if ($Candidates[$i] != 0)
	{
		print $i," is prime\n";
	}
}