Worst-case prime sieve

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)

• 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. :) – Alex Meiburg Aug 29 '15 at 1:37
• @AlexMeiburg, that looks like a useful answer. Maybe convert your comment to an answer? – D.W. Aug 31 '15 at 20:34

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.