Dynamic Sieve Algorithms for Prime Generation

I'm implementing开发者_如何转开发 the Sieve of Eratosthenes, for an explanation of this see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. However I would like to adapt it to generate M primes, not the primes 1 through N. My method of doing this is simply to create a large enough N such that all M primes are contained in this range. Does anyone have any good heuristics for modeling the growth of primes? In case you wish to post code snippets I am implementing this in Java and C++.

---

To generate M primes, you need to go up to about M log M. See Approximations for the nth prime number in this Wikipedia article about the Prime Number Theorem. To be on the safe side, you might want to overestimate -- say N = M (log M + 1).

Edited to add: As David Hammen points out, this overestimate is not always good enough. The Wikipedia article gives M (log M + log log M) as a safe upper bound for M >= 6.

---

This approximation of the nth prime is taken from wikipedia; therefore you'll just need to allocate an array of m*log(m)+m*log(log(m)); an array of m*log(m) will be unsufficient.

---

Another alternative is a segmented sieve. Sieve the numbers to a million. Then the second million. Then the third. And so on. Stop when you have enough.

It's not hard to reset the sieve for the next segment. See my blog for details.

---

Why not grow the sieve dynamically? Whenever you need more primes, re-allocate the seive memory, and run the sieve algorithm, just over the new space, using the primes that you have previously found.

---

Lazy evaluation comes to mind (such as Haskell and other functional languages do it for you). Although you a writing in an imperative language, you can apply the concept I think.

Consider the operation of removing the remaining cardinal numbers from the candidate set. Without actually touching the real algorithm (and more importantly without guessing how many numbers you will create), execute this operation in a lazy manner (which you will have to implement, because you're in an imperative language), when and if you try to take the smallest remaining number.