3
$\begingroup$

The Sieve of Eratosthenes bothers me because you have to specify an upper bound before you begin the algorithm.

Is there a prime sieve that doesn't require this?

More Formally:

Is it possible to write an iterator on which the i'th call to next() yields the prime number $p_i$ in only $O((p_i - p_{i-1})log(log(p_i)))$ time for all i > 1 ?

(Note: I'm looking for a worst-case solution, not amortized. For amortized time, you can simply use Sieve of Eratosthenes and restart the algorithm doubling n each time you hit the previous upper bound)

$\endgroup$
  • 1
    $\begingroup$ It seems that you could probably get something like this by incrementally extending your sieving. If you do so gradually enough, then you could get a good worse-case for each prime individually... e.g. hold a sieve up to 100, and you can estimate how much work it takes to get to 200. Each time it requests a prime between 1 and 100, do a fraction of that work. By the time you get to 200, you'll have it all "ready" and you can start on 200-400, etc., so that your worst-case is your amortized. 'll leave it someone with better math skills than I to figure how that performs exactly. :) $\endgroup$ – Alex Meiburg Aug 29 '15 at 1:37
  • $\begingroup$ @AlexMeiburg, that looks like a useful answer. Maybe convert your comment to an answer? $\endgroup$ – D.W. Aug 31 '15 at 20:34
2
$\begingroup$

Most fast sieves are segmented, so you can get this in efficient amortized time. When you call to get the next segment, you may have to increase the auxiliary prime list, but that's a trivial amount of time. Then you just sieve that segment, exactly how it would be done if you were sieving to some large known upper bound. You can wrap all of that in a next() call. I believe primesieve and primegen both have setups like this. This is also how my forprimes and forcomposites work, as well as my iterator in Perl/ntheory.

This is likely faster than prime-by-prime extensible sieves. I see in the Rosetta Code extensible prime generator task the C solution is a simple segmented generator like I mention above. The first D solution is the rather horrible method you noted. A number of the languages, including Go, implement O'Neill's lazy functional sieve which is more directly what you might be asking for. Ben Tilly shows a lazy sieve using closures in Perl here that should meet your complexity goal.

Of course you can do primality tests, but that takes more time than sieving until your input is large (how large depends on your implementations of both sieve and primality test, but it would certainly be before 10^25).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.