#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"