已关闭 。这个问题是基于观点的。它当前不接受答案。
想改善这个问题吗? 更新问题,以便通过编辑此帖子以事实和引用的形式回答。
4年前关闭。
什么是实现此功能的最佳方式:
ArrayList generatePrimes(int n)
此函数生成第一个n素数(edit:where n>1),因此generatePrimes(5)将返回ArrayListwith {2, 3, 5, 7, 11}。(我正在用C#进行此操作,但是我对Java实现很满意-或其他与此类似的语言(因此没有Haskell))
n
n>1
generatePrimes(5)
ArrayList
{2, 3, 5, 7, 11}
我确实知道如何编写此函数,但是昨晚当我这样做时,它并没有达到我希望的那样好。这是我想出的:
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; }
尽管我不希望速度明显低效,但我不太担心速度。我不介意使用哪种方法(天真或筛子或其他任何方法),但我确实希望它相当短并且很明显如何工作。
编辑 :感谢所有答复,尽管许多人没有回答我的实际问题。重申一下,我想要一段简洁的代码来生成素数列表。我已经知道如何使用多种方法来实现它,但是我倾向于编写不太清晰的代码。在此线程中,提出了一些好的选择:
BigInteger
nextProbablePrime
编辑2 :我已经在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]或等等。
6k+[1, 5]
30k+[1, 7, 11, 13, 17, 19, 23, 29]
Eratosthenes筛 (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; }