生成质数的最优雅方法
。这个问题是基于观点的。它当前不接受答案。
更新问题，以便通过编辑此帖子以事实和引用的形式回答。
4年前关闭。
什么是实现此功能的最佳方式：
ArrayList generatePrimes(int n)此函数生成第一个n素数（edit：where n>1），因此generatePrimes(5)将返回ArrayListwith {2,
3, 5, 7, 11}。（我正在用C＃进行此操作，但是我对Java实现很满意-或其他与此类似的语言（因此没有Haskell））
我确实知道如何编写此函数，但是昨晚当我这样做时，它并没有达到我希望的那样好。这是我想出的：
ArrayList generatePrimes(int toGenerate){
ArrayList primes = new ArrayList();
primes.Add(2);
primes.Add(3);
while (primes.Count < toGenerate)
{
int nextPrime = (int)(primes[primes.Count - 1]) + 2;
while (true)
{
bool isPrime = true;
foreach (int n in primes)
{
if (nextPrime % n == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
break;
}
else
{
nextPrime += 2;
}
}
primes.Add(nextPrime);
}
return primes;
}
尽管我不希望速度明显低效，但我不太担心速度。我不介意使用哪种方法（天真或筛子或其他任何方法），但我确实希望它相当短并且很明显如何工作。
：感谢所有答复，尽管许多人没有回答我的实际问题。重申一下，我想要一段简洁的代码来生成素数列表。我已经知道如何使用多种方法来实现它，但是我倾向于编写不太清晰的代码。在此线程中，提出了一些好的选择：
- 我最初拥有的版本的更好版本（Peter Smit，jmservera和Rekreativc）
- 一种非常干净的Eratosthenes（starblue）筛子的实现
- 使用Java
BigInteger和nextProbablePrime编写非常简单的代码，尽管我无法想象它特别有效（dfa） - 使用LINQ惰性生成素数列表（Maghis）
- 在文本文件中放入很多素数，并在必要时读入（普通话）
：我已经在C＃中实现了此处给出的几种方法，以及此处未提及的另一种方法。他们都有效地找到了前 n个
素数（而且我有一个不错的方法来确定要提供给筛子的极限值）。
回答：
非常感谢所有提供有用答案的人。这是我在C＃中找到前 n个
素数的几种不同方法的实现。前两种方法几乎是此处发布的方法。（海报名称在标题旁边。）我计划在某个时候进行Atkin筛分，尽管我怀疑这样做不会像现在的方法那样简单。如果有人能以任何方式改进这些方法，我很想知道:-)
（彼得·斯密特，jmservera，Rekreativc）
第一个素数是2。将其添加到素数列表中。下一个质数是下一个不能被该列表中的任何数字整除的数字。
public static List<int> GeneratePrimesNaive(int n){
List<int> primes = new List<int>();
primes.Add(2);
int nextPrime = 3;
while (primes.Count < n)
{
int sqrt = (int)Math.Sqrt(nextPrime);
bool isPrime = true;
for (int i = 0; (int)primes[i] <= sqrt; i++)
{
if (nextPrime % primes[i] == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
primes.Add(nextPrime);
}
nextPrime += 2;
}
return primes;
}
通过仅测试除数直到被测数的平方根来优化这一点；并仅测试奇数。这可以通过仅测试形式的数字来进一步优化6k+[1, 5]，或30k+[1, 7, 11,
13, 17, 19, 23,
29]或等等。
（starblue）
这将找到 k的
所有素数。为了列出前 n个
素数，我们首先需要近似第 n 个素数的值。如此处所述，可以使用以下方法执行此操作。
public static int ApproximateNthPrime(int nn){
double n = (double)nn;
double p;
if (nn >= 7022)
{
p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
}
else if (nn >= 6)
{
p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
}
else if (nn > 0)
{
p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
}
else
{
p = 0;
}
return (int)p;
}
// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
BitArray bits = new BitArray(limit + 1, true);
bits[0] = false;
bits[1] = false;
for (int i = 0; i * i <= limit; i++)
{
if (bits[i])
{
for (int j = i * i; j <= limit; j += i)
{
bits[j] = false;
}
}
}
return bits;
}
public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
int limit = ApproximateNthPrime(n);
BitArray bits = SieveOfEratosthenes(limit);
List<int> primes = new List<int>();
for (int i = 0, found = 0; i < limit && found < n; i++)
{
if (bits[i])
{
primes.Add(i);
found++;
}
}
return primes;
}
我最近才发现这种筛子，但是可以很简单地实现它。我的实现速度不及Eratosthenes筛，但是它比朴素的方法要快得多。
public static BitArray SieveOfSundaram(int limit){
limit /= 2;
BitArray bits = new BitArray(limit + 1, true);
for (int i = 1; 3 * i + 1 < limit; i++)
{
for (int j = 1; i + j + 2 * i * j <= limit; j++)
{
bits[i + j + 2 * i * j] = false;
}
}
return bits;
}
public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
int limit = ApproximateNthPrime(n);
BitArray bits = SieveOfSundaram(limit);
List<int> primes = new List<int>();
primes.Add(2);
for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
{
if (bits[i])
{
primes.Add(2 * i + 1);
found++;
}
}
return primes;
}
以上是 生成质数的最优雅方法 的全部内容， 来源链接： utcz.com/qa/423902.html
