java - 素数生成的动态筛选算法

Question

我正在实现埃拉托色尼筛法，对此的解释请参见 http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes .但是我想调整它以生成 M 个素数，而不是从 1 到 N 的素数。我这样做的方法只是创建一个足够大的 N，以便所有 M 个素数都包含在这个范围内。有没有人有任何好的启发式来模拟素数的增长？如果您想发布代码片段，我将使用 Java 和 C++ 实现。

Answer 1

要生成 M 个素数，您需要达到大约 M log M。参见 Approximations for the nth prime number在 this Wikipedia article关于素数定理。为了安全起见，您可能想要高估——比如 N = M (log M + 1)。

编辑补充:正如 David Hammen 指出的那样，这种高估并不总是足够好。维基百科文章给出了 M (log M + log log M) 作为 M >= 6 的安全上限。