[Edu-sig] Kirby Urner's Sieve of Eratosthenes

[Kirby Urner]

Tim Peters wrote:
>Note that this line can be written
>
>>             for i in range(prime ** 2, max + 1, prime):
>
>(that is, start at the square of the prime rather than twice the prime)
>instead for a substantial reduction in the total amount of work needed.  It
>should be an interesting exercise for students to figure out why this is a
>valid optimization!

I didn't see this at first, but yes -- if there's another
factor < prime, it'll already have been taken care of in
the elimination, so it's safe to start the range at prime**2.  

Plus there's the optimization of stopping with the 
elimination game altogether when prime**2 >= max (outermost 
loop) -- because high composites will have been crossed 
off by their lowest prime factors.

I've added your name to the marquee re those contributing
to the compactification of our Sieve of Erastosthenes
(http://www.inetarena.com/~pdx4d/ocn/numeracy2.html)

Here's the code as of now:

def erastosthenes(n):
   """A prime number sieve, returns list of primes <= n
   
   Thanks to Erastosthenes for the algorithm, with
   streamlining by Ka-Ping Yee, John Posner and Tim Peters"""
   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))

Kirby