素数生成的动态筛选算法

Question

我正在实现Eratosthenes的筛子，有关这方面的解释，请参阅http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes。然而，我想调整它来生成M个素数，而不是1到N个素数。我这样做的方法很简单，就是创建一个足够大的N，使得所有M个素数都包含在这个范围内。有谁有好的启发式方法来模拟素数的增长？如果你想发布代码片段，我用Java和C++实现。

Answer 1

要生成M个素数，您需要达到约M log M。请参阅this Wikipedia article中关于素数定理的Approximations for the nth prime number。为了安全起见，您可能希望高估--比方说N=M (log + 1)。

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

Answer 2

​

​

第n个素数的近似值取自wikipedia；因此，您只需要分配一个m*log(m)+m*log(log(m))数组；一个m*log(m)数组是不够的。

Answer 3

另一种选择是分段筛子。把数字筛选到一百万。然后是第二个百万。然后是第三个。诸若此类。当你吃够了就停下来。

为下一段重新设置筛子并不难。请参阅我的blog了解详细信息。