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

[Tim Peters]

[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