[Tutor] primes - sieve of odds

C Smith smichr at hotmail.com
Thu Mar 24 06:44:31 CET 2005

>> Now it would be fine to have an *equally fast*
>> infinite prime number generator.
>> Has anybody any suggestions?
> 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:

Take a look!


More information about the Tutor mailing list