[Tutor] primes - sieve of odds

John Miller jmillr at umich.edu
Sat Mar 26 17:23:13 CET 2005


On Mar 24, 2005, at 6:01 AM, C Smith <smichr at hotmail.com> wrote:

>> What follows is an attempt based on the previous tutor-evolved sieve
>> that extends the range in which to find the next prime by a factor of
>> 2 over the last known prime. A similar algorithm is on ASPN (I
>> bellieve), under
>>
>> Space-efficient version of sieve of Eratosthenes.
>> D. Eppstein, May 2004
>>
> Oh, please...ignore what I suggested and look at Eppstein's code. It's
> a thing of beauty and just keeps chugging out primes well past what the
> inefficient version that I suggested could do with the same memory.
> It's a "tortoise and hare" race as the memory gets chewed up by the
> esieve approach.
>
> The ASPN version of Eppstein's program is an older one than the one at
> the following site:
> http://www.ics.uci.edu/~eppstein/PADS/Eratosthenes.py

How does one actually use this module? For example:

 >>> import eratosthenes
 >>> eratosthenes.primes()
<generator object at 0x640d0>
 >>> eratosthenes.primes().next()
2
 >>> eratosthenes.primes().next()
2
 >>> eratosthenes.primes().next()
2

How does one get beyond the first prime?

Thanks,

John



More information about the Tutor mailing list