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

[Ka-Ping Yee]

On Mon, 5 Jun 2000, Kirby Urner wrote:
> In fact, I'd go even further and say it's the essence of
> the Erastosthenes method that we _do not_ try to figure 
> out if 13 (for example) goes evenly into some gnarly 
> multi-digit number -- nor should we ask the computer 
> this question.

This makes sense to me.  Similarly, the use of square root
seems like asking a bit much.

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))


-- ?!ng