Entry

What is the Python code that will print primes below 1000?

Jun 16th, 2000 10:48
Dan Gindikin, unknown unknown, http://www.inetarena.com/~pdx4d/ocn/numeracy2.html#sieve

initial answer:

import re
for n in range(2, 1000):
    if not re.match('(11+)\\1+$', '1'*n):
        print n

and then again:

While the above submission is an interesting
application of regular expressions, it's not really
the way to get a list of primes.  Below is primes.py,
taken from the standard distribution that is faster
by a factor of 10-20:

primesuspects = range(3,1000,2)
ptr = 0
while ptr < len(primesuspects):
  val = primesuspects[ptr]
  for i in primesuspects[ptr+1:]:
    if not i % val:
      primesuspects.remove(i)
  ptr = ptr + 1
print primesuspects

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The standard way to find primes below a certain number is to use the 
Sieve of Erastosthenes:

def erastosthenes(n):
   "A prime number sieve, returns list of primes <= n"
   sieve = [0, 0] + [1] * n   # [0 0 1 1 1...]
   prime = 2                  # initial prime
   while prime**2 <= n:
       for i in range(prime**2, n+1, prime): 
            sieve[i] = 0      # step through sieve by prime
       prime = prime+1 + sieve[prime+1:].index(1) # get next prime
   # filter grabs corresponding range members only when seive = 1
   return filter(lambda i, sieve=sieve: sieve[i], range(n+1))

it is about 2 to 3 times faster than the solution above for n=1000. The 
difference in running time becomes significantly more pronounced for 
larger n.