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

[Kirby Urner]

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