用于素数生成的动态筛选算法
我正在实现埃拉托斯特尼筛法，有关对此的解释，请参阅http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes。然而，我想对其进行调整以生成 M 个素数，而不是素数 1 到 N。我这样做的方法只是创建一个足够大的 N，以便所有 M 个素数都包含在这个范围内。有人有任何好的启发式来模拟素数的增长吗？如果您希望发布代码片段，我将使用 Java 和 C++ 实现此功能。
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++.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
要生成 M 个素数，您需要大约 M log M。请参阅第 n 个素数的近似值 在 这篇关于素数定理的维基百科文章。为了安全起见，您可能需要高估——比如 N = M (log M + 1)。
编辑补充：正如 David Hammen 指出的那样，这种高估并不总是足够好。维基百科文章给出 M (log M + log log M) 作为 M >= 6 的安全上限。
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.
这个第 n 个素数的近似值取自维基百科；因此，您只需要分配一个 m*log(m)+m*log(log(m)) 数组；
m*log(m)数组是不够的。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 ofm*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.
为什么不动态增大筛子呢？每当您需要更多素数时，请重新分配 seive 内存，并使用您之前找到的素数在新空间上运行筛选算法。
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.
我想到了惰性求值（例如 Haskell 和其他函数式语言为你做的事情）。虽然你是用命令式语言写作，但你可以应用我认为的概念。
考虑从候选集中删除剩余基数的操作。在不实际接触真正的算法的情况下（更重要的是，无需猜测您将创建多少个数字），以惰性方式执行此操作（您必须实现该操作，因为您当您尝试获取最小的剩余数字时（您使用的是命令式语言）。
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.