最优雅的方式来生成素数 [英] Most elegant way to generate prime numbers
问题描述
什么是实现这一功能的最优雅的方式：
What is the most elegant way to implement this function:
ArrayList generatePrimes(int n)
这个函数产生的第一个 N 素数（编辑：其中 N'GT; 1 ），所以 generatePrimes（5）将返回的ArrayList 与 {2，3，5，7，11} 。 （我在做这在C＃中，但我很高兴用Java实现 - 或与此有关的任何其他类似的语言（所以不哈斯克尔））。
This function generates the first n primes (edit: where n>1), so generatePrimes(5) will return an ArrayList with {2, 3, 5, 7, 11}. (I'm doing this in C#, but I'm happy with a Java implementation - or any other similar language for that matter (so not Haskell)).
我不知道该怎么写这个功能，但是当我做到了，昨晚并没有落得像你一样，我希望。以下是我想出了：
I do know how to write this function, but when I did it last night it didn't end up as nice as I was hoping. Here is what I came up with:
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;
}
我不是太在意速度的，虽然我不希望它是明显的低效率。我不介意使用哪种方法（幼稚或筛或其他任何东西），但我想它是相当短的和明显的效果如何。
I'm not too concerned about speed, although I don't want it to be obviously inefficient. I don't mind which method is used (naive or sieve or anything else), but I do want it to be fairly short and obvious how it works.
修改：感谢所有谁已作出回应，但许多没有回答我的实际问题。要重申的是，我想要一个干净的一块code生成素数的列表。我已经知道该怎么做了一堆不同的方式，但我倾向于写code是不明确的，因为它可以。在这个线程几个不错的选项已被提出：
Edit: Thanks to all who have responded, although many didn't answer my actual question. To reiterate, I wanted a nice clean piece of code that generated a list of prime numbers. I already know how to do it a bunch of different ways, but I'm prone to writing code that isn't as clear as it could be. In this thread a few good options have been proposed:
- 是我原来有一个更好的版本（彼得·斯密特，jmservera和Rekreativc）
- 在一个很干净的实现埃拉托色尼（starblue） 的筛
- 使用Java的
的BigInteger和nextProbablePrime非常简单code，但我无法想象它是特别有效的（DFA） - 使用LINQ懒洋洋地生成素数的列表（Maghis）
- 把很多素数在一个文本文件，并宣读他们在必要时（达林）
- A nicer version of what I originally had (Peter Smit, jmservera and Rekreativc)
- A very clean implementation of the sieve of Eratosthenes (starblue)
- Use Java's
BigIntegers andnextProbablePrimefor very simple code, although I can't imagine it being particularly efficient (dfa) - Use LINQ to lazily generate the list of primes (Maghis)
- Put lots of primes in a text file and read them in when necessary (darin)
编辑2 ：我有<一个href="http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1072205#1072205">implemented在C＃中的一对夫妇在这里给出的方法，而另一种方法，此处不再赘述。他们都找到第一个的 N 的素数有效的（我有一个<一个href="http://stackoverflow.com/questions/1042717/is-there-a-way-to-find-the-approximate-value-of-the-nth-prime/1069023#1069023">decent找到限制提供给筛）的方法。
Edit 2: I've implemented in C# a couple of the methods given here, and another method not mentioned here. They all find the first n primes effectively (and I have a decent method of finding the limit to provide to the sieves).
推荐答案
非常感谢所有谁给了有用的答案。这里是我的发现第一次的 N 的素数在C＃中的几种不同的方法实现。前两种方法是pretty的很多东西在这里被张贴。 （海报名称旁边的称号。）我打算做阿特金的筛的某个时候，但我怀疑这会不会是那么简单的方法，在这里当前。如果任何人都可以看到任何方式提高任何这些方法我很想知道： - ）
Many thanks to all who gave helpful answers. Here are my implementations of a few different methods of finding the first n primes in C#. The first two methods are pretty much what was posted here. (The posters names are next to the title.) I plan on doing the sieve of Atkin sometime, although I suspect it won't be quite as simple as the methods here currently. If anybody can see any way of improving any of these methods I'd love to know :-)
标准方法（<一href="http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1043007#1043007">Peter斯密特，<一个href="http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1043002#1043002">jmservera, <一href="http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1042969#1042969">Rekreativc)
第一素数是2。此加入素数的列表。下一任是下一个数字，它是不是由任何数量的这份榜单上整除。
The first prime number is 2. Add this to a list of primes. The next prime is the next number that is not evenly divisible by any number on this list.
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] 或等。
This has been optimised by only testing for divisibility up to the square root of the number being tested; and by only testing odd numbers. This can be further optimised by testing only numbers of the form 6k+[1, 5], or 30k+[1, 7, 11, 13, 17, 19, 23, 29] or so on.
埃拉托色尼的筛（<一href="http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1043247#1043247">starblue)
此找到所有的质数来的 K 的。为了让第一次的 N 的素数的列表，我们首先需要接近* N *次贷的价值。以下的方法，<一href="http://stackoverflow.com/questions/1042717/is-there-a-way-to-find-the-approximate-value-of-the-nth-prime/1069023#1069023">as这里描述，做到这一点。
This finds all the primes to k. To make a list of the first n primes, we first need to approximate value of the *n*th prime. The following method, as described here, does this.
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;
}
孙达拉姆的筛
我只发现此筛的最近，但它可以很简单地实现。我的实现是不一样快埃拉托色尼的筛子，但它比幼稚的方法显著快。
I only discovered this sieve recently, but it can be implemented quite simply. My implementation isn't as fast as the sieve of Eratosthenes, but it is significantly faster than the naive method.
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;
}
这篇关于最优雅的方式来生成素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
