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)

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).

StackExchange Computer Science Q#45669, answer score: 2