最优雅的方式来生成素数

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) = n / log(n)

对于最多n个素数的数量，找到一个限制，然后使用筛子。估计低估了n的素数，因此筛子将略大于必要的，这是可以的。

这是我的标准Java筛选器，在普通笔记本电脑上计算出大约一秒钟的第一百万个素数：

public static BitSet computePrimes(int limit){
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++)
    {
        if (primes.get(i))
        {
            for (int j = i * i; j < limit; j += i)
            {
                primes.clear(j);
            }
        }
    }
    return primes;}

Answer 2

非常感谢所有给出有益答案的人。以下是我在C＃中查找前n个素数的几种不同方法的实现。前两种方法几乎就是这里发布的内容。（海报名称在标题旁边。）我计划在某个时候对阿特金进行筛选，尽管我怀疑它不会像现在的方法那么简单。如果有人能够看到任何改进这些方法的方法我都很想知道:-)

标准方法（彼得·斯密特，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]或等等。

Eratosthenes筛（星蓝）

这找到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 limitpublic 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;}

筛选Sundaram

我最近才发现这个筛子，但它可以很简单地实现。我的实施并不像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;}

Answer 3

重新解决一个老问题，但我在玩LINQ时偶然发现了它。

此代码需要带有并行扩展的.NET4.0或.NET3.5

public List<int> GeneratePrimes(int n) {
    var r = from i in Enumerable.Range(2, n - 1).AsParallel()
            where Enumerable.Range(2, (int)Math.Sqrt(i)).All(j => i % j != 0)
            select i;
    return r.ToList();}