[Tutor] primes - sieve of odds
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
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