#This line is used to invoke the interpreter for cgi scripts
# //////////////////////////////////////////////////////////
# // Name: Peter M. Maurer
# // Program: Sieve of Eratosthenes
# // Due: Never
# // Language: Ruby
# //////////////////////////////////////////////////////////

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