4
$\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$
4
  • 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$ Aug 29, 2015 at 1:37
  • $\begingroup$ @AlexMeiburg, that looks like a useful answer. Maybe convert your comment to an answer? $\endgroup$
    – D.W.
    Aug 31, 2015 at 20:34
  • $\begingroup$ There are some use cases where doubling is absolutely not possible. For example, you want to examine all primes up to 10^15. Your partial sieve can only contain a limited amount of data. Like covering a few trillion numbers if you spend a few thousand dollars on a computer. $\endgroup$
    – gnasher729
    Oct 31, 2022 at 8:59
  • $\begingroup$ If you need to limit worst case and amortised time is not acceptable, then you just build the next sieve bit by bit. You have a complete sieve and are working on the next sieve. Every time you are asked for the next prime you do some amount of work on the next sieve. For example you have a sieve for the next million odd numbers, so when I ask you for a prime you remove the next 100 multiples of 3, 100 more on the next call, after 3333 calls you switch to removing multiples of 5 and so on. Calculated so when I ask for the last prime in the first sieve, you finish building the second sieve. $\endgroup$
    – gnasher729
    Nov 1, 2022 at 10:10

3 Answers 3

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$
0
$\begingroup$

What you are after is called an "incremental sieve" in the literature. The sieve of Bengalloun does a little better than what you have requested: it only requires $O(p_i - p_{i-1})$ time, and can be sped up by a $\log\log p_i$ factor. The article is paywalled, but there is a nice brief description of the algorithm in Paul Pritchard, "Linear Prime-Number Sieves: a Family Tree, Science of Computer Programming, vol. 9 (1987) pp.17-35.

$\endgroup$
0
$\begingroup$

That's actually just a bit of clever programming; I wouldn't even call it "computer science". Create a data structure that you call a sieve. For example, using one byte for the numbers from 30k to 30k + 29 to indicate which of 30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23 and 30k+29 are primes. At any point in time, you store two values 30k and 30k', and allocate (k' - k) bytes of memory indicating which primes there are in the interval 30k ≤ p < 30k'.

If you want to know if p is a prime: If p < 10 then 2, 3, 5, 7 are primes. Otherwise write p = 30k + n, 0 ≤ n < 30. If n mod 30 ≠ 1, 7, 11, 13, 17, 19, 23, 29 then n is not prime. If 30k + n is not in the stored range then recreate a sieve with a different starting point. But most likely you just look up one bit in a sieve.

Depending on your use, you may always store bits for small primes because you will often need them, plus bytes for some additional range which is variable. And when you change the stored range, make sure there is some overlap - if your sieve stored numbers from 3 trillion to 3 trillion + 299,999 then you don't want to recalculate a sieve if I examine p, p+1, p-1, p, p+1, p-1 etc. with p at the end or the start of your sieve.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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