用于素数生成的动态筛选算法 [英] Dynamic Sieve Algorithms for Prime Generation

问题描述

我正在实施Eratosthenes筛网，有关此说明，请参见> 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++.

推荐答案

要生成M个质数，您需要上升到大约M logM。请参见第n个质数的近似值。 = http://en.wikipedia.org/wiki/Prime_number_theorem rel = nofollow>此Wikipedia文章关于素数定理。为了安全起见，您可能需要高估-例如N = M（log M +1）。

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).

编辑后添加：正如David Hammen指出的那样，这种高估并不总是足够好。 Wikipedia文章将M（log M + log log M）作为M> = 6的安全上限。

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.

这篇关于用于素数生成的动态筛选算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！