#There could be a line here to invoke the interpreter if used in cgi
# //////////////////////////////////////////////////////////
# // Name: Peter M. Maurer
# // Program: Sieve of Eratosthenes
# // Due: Never
# // Language: Python
# //////////////////////////////////////////////////////////

# define the sieve data structure
Candidates = [1]
for i in range(1000):
    # everything is potentially prime until proven otherwise
    Candidates.append(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 and Candidates[i] == 0:
        i = i+1
    # 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[i*j] = 0
            j = j+1
    # advance to the next candidate
    i = i+1
# all uncrossed-out numbers are prime (and only those numbers)
# print all primes
for i in range(1000):
    if Candidates[i] != 0:
        print i," is prime"