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

Kirby Urner pdx4d@teleport.com
Mon, 05 Jun 2000 19:51:19 -0700

```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.

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

```