[Edu-sig] Kirby Urner's Sieve of Eratosthenes
Tim Peters
tim_one@email.msn.com
Mon, 5 Jun 2000 21:30:30 -0400
[Ka-Ping Yee. defending the arithmetic purity of The Sieve]
> ...
> 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):
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!
> sieve[i] = 0
> while prime < max:
> prime = prime + 1
> if sieve[prime]: break
> return filter(lambda i, sieve=sieve: sieve[i], range(max + 1))
>
>
> -- ?!ng