# [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