#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