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

Kirby Urner pdx4d@teleport.com
Mon, 05 Jun 2000 16:28:52 -0700

```Ka-Ping Yee wrote:
>You can use the "filter" function to obtain your results
>at the end, and you can use the third argument to the
>"range" function to perform the stepping more succinctly
>and clearly:
>
>    def eratosthenes(max):
>        sieve = [0, 0] + [1] * max
>        prime = 2
>        while prime < max:
>            for i in range(prime * 2, max + 1, prime):
>                sieve[i] = 0
>            while prime < max:
>                prime = prime + 1
>                if sieve[prime]: break
>        return filter(lambda i, sieve=sieve: sieve[i], range(max + 1))
>

This I like quite a bit!  Good job.

I'd probably keep the cut-off at 2nd root, even if I don't
use root function, plus given the preponderance of 0s after
awhile, I'd like to use the list.index(n) primitive to search
a sliced sieve for the next 1, vs stepping by 1 through a
break loop, i.e.:

def erastosthenes(max):  # with thanks to Ka-Ping Yee
"""Sieve of Erastosthenes"""
sieve = [0, 0] + [1] * max
prime = 2
while prime*prime <= max:
for i in range(prime * 2, max + 1, prime):
sieve[i] = 0
prime = prime+1 + sieve[prime+1:].index(1)
return filter(lambda i, final=sieve: final[i], range(max + 1))

Ka-Ping, if you have no objection, maybe I'll swap in the
above on http://www.inetarena.com/~pdx4d/ocn/numeracy2.html ?

Note: also change var name to final in the lamda, as
sieve=sieve looks more cryptic IMO.

Kirby

```