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

Question

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

Answer 1

要生成 M 个素数，您需要上升到大约 M log M。请参阅这篇关于素数定理的维基百科文章中第 n 个素数的近似值。为了安全起见，您可能需要高估——比如 N = M (log M + 1)。

编辑补充：正​​如大卫哈门指出的那样，这种高估并不总是足够好。Wikipedia 文章将 M (log M + log log M) 作为 M >= 6 的安全上限。

Answer 2

第 n 个素数的近似值取自维基百科；因此你只需要分配一个数组m*log(m)+m*log(log(m))；一个数组m*log(m)将是不够的。

Answer 3

另一种选择是分段筛。将数字筛选到一百万。然后是第二个百万。然后是第三个。等等。当你有足够的时候停下来。

为下一段重新设置筛子并不难。有关详细信息，请参阅我的博客。

Answer 4

为什么不动态增长筛子？每当您需要更多素数时，重新分配筛选内存，并使用您之前找到的素数在新空间上运行筛选算法。

Answer 5

想到惰性求值（例如 Haskell 和其他函数式语言为您做）。尽管您使用命令式语言写作，但您可以应用我认为的概念。

考虑从候选集中删除剩余基数的操作。无需实际接触真正的算法（更重要的是无需猜测您将创建多少个数字），以惰性方式执行此操作（您必须实现，因为您使用的是命令式语言），何时以及是否尝试取最小的剩余数。