最优雅的方式来生成素数

Question

最优雅的方式来生成素数

实现此功能的最佳方式是什么：

ArrayList generatePrimes(int n)

此函数生成第一个n素数（编辑：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（星蓝）筛的非常干净的实施

• 使用Java BigInteger和nextProbablePrime非常简单的代码，虽然我无法想象它特别有效（dfa）

• 使用LINQ懒惰地生成素数列表（Maghis）

• 将大量素数放入文本文件中并在必要时读取（darin）

Answer 1

使用估算值pi(n)&nbsp;=&nbsp;n&nbsp;/&nbsp;log(n)对于最多n个素数的数量，找到一个限制，然后使用筛子。估计低估了n的素数，因此筛子将略大于必要的，这是可以的。这是我的标准Java筛选器，在普通笔记本电脑上计算出大约一秒钟的第一百万个素数：public&nbsp;static&nbsp;BitSet&nbsp;computePrimes(int&nbsp;limit){ &nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;BitSet&nbsp;primes&nbsp;=&nbsp;new&nbsp;BitSet(); &nbsp;&nbsp;&nbsp;&nbsp;primes.set(0,&nbsp;false); &nbsp;&nbsp;&nbsp;&nbsp;primes.set(1,&nbsp;false); &nbsp;&nbsp;&nbsp;&nbsp;primes.set(2,&nbsp;limit,&nbsp;true); &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;*&nbsp;i&nbsp;<&nbsp;limit;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(primes.get(i)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;j&nbsp;=&nbsp;i&nbsp;*&nbsp;i;&nbsp;j&nbsp;<&nbsp;limit;&nbsp;j&nbsp;+=&nbsp;i) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;primes.clear(j); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;primes;}

Answer 2

非常感谢所有给出有益答案的人。以下是我在C＃中查找前n个素数的几种不同方法的实现。前两种方法几乎就是这里发布的内容。（海报名称在标题旁边。）我计划在某个时候对阿特金进行筛选，尽管我怀疑它不会像现在的方法那么简单。如果有人能够看到任何改进这些方法的方法我都很想知道:-)标准方法（彼得·斯密特，jmservera，Rekreativc）第一个素数是2.将其添加到素数列表中。下一个素数是下一个数字，该数字不能被此列表中的任何数字整除。public&nbsp;static&nbsp;List<int>&nbsp;GeneratePrimesNaive(int&nbsp;n){ &nbsp;&nbsp;&nbsp;&nbsp;List<int>&nbsp;primes&nbsp;=&nbsp;new&nbsp;List<int>(); &nbsp;&nbsp;&nbsp;&nbsp;primes.Add(2); &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;nextPrime&nbsp;=&nbsp;3; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(primes.Count&nbsp;<&nbsp;n) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;sqrt&nbsp;=&nbsp;(int)Math.Sqrt(nextPrime); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bool&nbsp;isPrime&nbsp;=&nbsp;true; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;(int)primes[i]&nbsp;<=&nbsp;sqrt;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(nextPrime&nbsp;%&nbsp;primes[i]&nbsp;==&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;isPrime&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(isPrime) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;primes.Add(nextPrime); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nextPrime&nbsp;+=&nbsp;2; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;primes;}通过仅测试可测试数字的平方根的可分性来优化这一点;&nbsp;并且只测试奇数。这可以通过测试形式的只有数字来进一步优化6k+[1, 5]，或30k+[1, 7, 11, 13, 17, 19, 23, 29]或等等。Eratosthenes筛（星蓝）这找到k的所有素数。为了列出前n个素数，我们首先需要近似第n个素数的值。如此处所述，以下方法可以做到这一点。public&nbsp;static&nbsp;int&nbsp;ApproximateNthPrime(int&nbsp;nn){ &nbsp;&nbsp;&nbsp;&nbsp;double&nbsp;n&nbsp;=&nbsp;(double)nn; &nbsp;&nbsp;&nbsp;&nbsp;double&nbsp;p; &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(nn&nbsp;>=&nbsp;7022) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;n&nbsp;*&nbsp;Math.Log(n)&nbsp;+&nbsp;n&nbsp;*&nbsp;(Math.Log(Math.Log(n))&nbsp;-&nbsp;0.9385); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if&nbsp;(nn&nbsp;>=&nbsp;6) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;n&nbsp;*&nbsp;Math.Log(n)&nbsp;+&nbsp;n&nbsp;*&nbsp;Math.Log(Math.Log(n)); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if&nbsp;(nn&nbsp;>&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;new&nbsp;int[]&nbsp;{&nbsp;2,&nbsp;3,&nbsp;5,&nbsp;7,&nbsp;11&nbsp;}[nn&nbsp;-&nbsp;1]; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(int)p;}//&nbsp;Find&nbsp;all&nbsp;primes&nbsp;up&nbsp;to&nbsp;and&nbsp;including&nbsp;the&nbsp;limitpublic&nbsp;static&nbsp;BitArray&nbsp;SieveOfEratosthenes(int&nbsp;limit){ &nbsp;&nbsp;&nbsp;&nbsp;BitArray&nbsp;bits&nbsp;=&nbsp;new&nbsp;BitArray(limit&nbsp;+&nbsp;1,&nbsp;true); &nbsp;&nbsp;&nbsp;&nbsp;bits[0]&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;bits[1]&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;*&nbsp;i&nbsp;<=&nbsp;limit;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(bits[i]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;j&nbsp;=&nbsp;i&nbsp;*&nbsp;i;&nbsp;j&nbsp;<=&nbsp;limit;&nbsp;j&nbsp;+=&nbsp;i) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bits[j]&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;bits;}public&nbsp;static&nbsp;List<int>&nbsp;GeneratePrimesSieveOfEratosthenes(int&nbsp;n){ &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;limit&nbsp;=&nbsp;ApproximateNthPrime(n); &nbsp;&nbsp;&nbsp;&nbsp;BitArray&nbsp;bits&nbsp;=&nbsp;SieveOfEratosthenes(limit); &nbsp;&nbsp;&nbsp;&nbsp;List<int>&nbsp;primes&nbsp;=&nbsp;new&nbsp;List<int>(); &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0,&nbsp;found&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;limit&nbsp;&&&nbsp;found&nbsp;<&nbsp;n;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(bits[i]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;primes.Add(i); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;found++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;primes;}筛选Sundaram我最近才发现这个筛子，但它可以很简单地实现。我的实施并不像Eratosthenes的筛子快，但它比天真的方法快得多。public&nbsp;static&nbsp;BitArray&nbsp;SieveOfSundaram(int&nbsp;limit){ &nbsp;&nbsp;&nbsp;&nbsp;limit&nbsp;/=&nbsp;2; &nbsp;&nbsp;&nbsp;&nbsp;BitArray&nbsp;bits&nbsp;=&nbsp;new&nbsp;BitArray(limit&nbsp;+&nbsp;1,&nbsp;true); &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;1;&nbsp;3&nbsp;*&nbsp;i&nbsp;+&nbsp;1&nbsp;<&nbsp;limit;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;j&nbsp;=&nbsp;1;&nbsp;i&nbsp;+&nbsp;j&nbsp;+&nbsp;2&nbsp;*&nbsp;i&nbsp;*&nbsp;j&nbsp;<=&nbsp;limit;&nbsp;j++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bits[i&nbsp;+&nbsp;j&nbsp;+&nbsp;2&nbsp;*&nbsp;i&nbsp;*&nbsp;j]&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;bits;}public&nbsp;static&nbsp;List<int>&nbsp;GeneratePrimesSieveOfSundaram(int&nbsp;n){ &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;limit&nbsp;=&nbsp;ApproximateNthPrime(n); &nbsp;&nbsp;&nbsp;&nbsp;BitArray&nbsp;bits&nbsp;=&nbsp;SieveOfSundaram(limit); &nbsp;&nbsp;&nbsp;&nbsp;List<int>&nbsp;primes&nbsp;=&nbsp;new&nbsp;List<int>(); &nbsp;&nbsp;&nbsp;&nbsp;primes.Add(2); &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;1,&nbsp;found&nbsp;=&nbsp;1;&nbsp;2&nbsp;*&nbsp;i&nbsp;+&nbsp;1&nbsp;<=&nbsp;limit&nbsp;&&&nbsp;found&nbsp;<&nbsp;n;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(bits[i]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;primes.Add(2&nbsp;*&nbsp;i&nbsp;+&nbsp;1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;found++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;primes;}

Answer 3

重新解决一个老问题，但我在玩LINQ时偶然发现了它。此代码需要带有并行扩展的.NET4.0或.NET3.5public&nbsp;List<int>&nbsp;GeneratePrimes(int&nbsp;n)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;r&nbsp;=&nbsp;from&nbsp;i&nbsp;in&nbsp;Enumerable.Range(2,&nbsp;n&nbsp;-&nbsp;1).AsParallel() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;where&nbsp;Enumerable.Range(2,&nbsp;(int)Math.Sqrt(i)).All(j&nbsp;=>&nbsp;i&nbsp;%&nbsp;j&nbsp;!=&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;select&nbsp;i; &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;r.ToList();}