生成质数的最优雅方法

Question

如何最优雅地实现这个函数：

ArrayList generatePrimes(int n)

这个函数生成前{{n}}个质数（编辑：其中{{n>1}}），所以generatePrimes(5)将返回一个ArrayList，其中包含{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）
• 一个非常干净的埃拉托色尼筛法实现（starblue）
• 使用Java的BigInteger和nextProbablePrime来编写非常简单的代码，尽管我无法想象它特别高效（dfa）
• 使用LINQ来懒惰地生成质数列表（Maghis）
• 在文本文件中放置大量质数，并在必要时读取它们（darin）

编辑 2: 我已经在 C# 中实现了这里给出的一些方法，还有另一种方法没有在这里提到。它们都可以有效地找到前n个质数（我有一个不错的方法来找到提供给筛子的限制）。

- David Johnstone

---

最好返回一个IEnumerable<int>并逐个yield。 - Felice Pollano

我想知道生成质数的最不优雅的方式是什么。我在考虑是否涉及使用Access数据库？ - j_random_hacker

对比一下，这是BMeph在2008年写的Haskell代码：nubBy (((>1).).gcd) [2..]。它只保留自然数中从2开始的非重复数字，同时将任何与先前找到的数字之一的gcd大于1的数字视为重复。它非常低效，产生的质数数量平方级增长。但它很优雅。 - Will Ness

在我看来，最优雅的语言是Haskell，它的代码如下：import Data.List.Ordered ; let { _Y g = g (_Y g) ; primes = 2 : _Y( (3:) . minus [5,7..] . unionAll . map (\p-> [p*p, p*p+p*2..]) ) } 当然，这完全基于个人观点。 - Will Ness

你要寻找什么类型的质数？它们需要通过哪些测试？ - jww

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;
}

- starblue

---

这是一个非常好的埃拉托斯特尼筛法的实现。 - David Johnstone

在外层循环中，只需要循环到 i <= Math.sqrt(limit) 不就可以了吗？ - Christoph

@David Johnstone 不，pi(n) = n / log(n) 低估了n以内质数的数量，这与实际相反。不过我很高兴你找到了一个更好的近似值。 - starblue

如果你愿意在自己的循环中删除所有2的倍数，你可以使用j+= 2 * i作为循环增量来节省一些额外的运行时间，并且你可以使用位移运算符计算一次。 - Nick Larsen

通过用一个实现2、3和5的轮式分解的类替换BitSet，其速度几乎提高了3倍。 - starblue

Answer 2

感谢所有提供有用答案的人。以下是我在C＃中找到前n个质数的几种不同方法的实现。前两种方法与此处发布的内容基本相同。（发布者名称位于标题旁边。）我计划随时进行Atkin筛选，尽管我怀疑这不会像目前这里的方法那样简单。如果有人能看到任何改进这些方法的方法，我会很乐意知道:-）

标准方法 (Peter Smit, 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;
}

桑达拉姆筛法

我最近才发现这个筛法，但它可以被相当简单地实现。我的实现虽然不如埃拉托斯特尼筛法快，但比朴素方法快得多。

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;
}

- David Johnstone

---

FYI - 我不得不将你的主循环计数器更改为 "for (int i = 0; i * i <= limit && i * i > 0; i ++)"，以防止溢出。 - Jacobs Data Solutions

这个Sundaram筛法的实现是非常少数正确的之一。大多数实现在计算i+j+2*i*j时使用错误的界限，导致输出不正确。 - jahackbeth

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(1, (int)Math.Sqrt(i)).All(j => j == 1 || i % j != 0)
            select i;
    return r.ToList();
}

- spookycoder

---

为什么这不是被采纳的答案？这里的代码比被采纳的答案的代码更短、更优雅，而且速度更快。真希望我可以投多个赞！ - Avrohom Yisroel

代码越短并不意味着越好。如果是这样的话，我们都会写 Perl 了。 - gbjbaanb

Answer 4

你已经在正确的道路上。

一些评论

• primes.Add(3); 使得该函数不适用于数字 = 1。

• 你并不需要测试使用质数大于待测试数字的平方根进行除法运算。

建议的代码：

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();

    if(toGenerate > 0) primes.Add(2);

    int curTest = 3;
    while (primes.Count < toGenerate)
    {

        int sqrt = (int) Math.sqrt(curTest);

        bool isPrime = true;
        for (int i = 0; i < primes.Count && primes.get(i) <= sqrt; ++i)
        {
            if (curTest % primes.get(i) == 0)
            {
                isPrime = false;
                break;
            }
        }

        if(isPrime) primes.Add(curTest);

        curTest +=2
    }
    return primes;
}

- Peter Smit

---

在循环中测试 prime*prime <= curTest 而不是预先计算平方根可能会使其更快，并且会使其更通用（适用于大数等）。 - yairchu

为什么要使用平方根？这种选项的数学背景是什么？我可能只会简单地除以2。 - Luis Filipe

因为如果一个数有质因数，那么其中至少有一个质因数必须小于等于它的平方根。如果a * b = c且a <= b，则a <= sqrt(c) <= b。 - David Johnstone

Answer 5

你应该看一下可能质数。特别是要看随机算法和Miller-Rabin素性测试。

为了完整起见，你可以使用java.math.BigInteger：

public class PrimeGenerator implements Iterator<BigInteger>, Iterable<BigInteger> {

    private BigInteger p = BigInteger.ONE;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public BigInteger next() {
        p = p.nextProbablePrime();
        return p;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public Iterator<BigInteger> iterator() {
        return this;
    }
}

@Test
public void printPrimes() {
    for (BigInteger p : new PrimeGenerator()) {
        System.out.println(p);
    }
}

- dfa

---

Miller-Rabbin非常快速，代码也非常简单。给它足够的迭代次数可以使其可靠性足以与随机CPU故障竞争，以确定误报的可能性。该算法的缺点是理解其实际工作原理是一项困难的任务。 - Brian

Answer 6

绝不高效，但也许是最易读的：

public static IEnumerable<int> GeneratePrimes()
{
   return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
                                     .All(divisor => candidate % divisor != 0));
}

使用：

public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
   for (int i = from; i <= to; i++) yield return i;
}

实际上，这只是一些帖子的变体，格式更好而已。

- RaphM

Answer 7

版权所有2009年由St.Wittum 13189 Berlin GERMANY根据CC-BY-SA许可证 https://creativecommons.org/licenses/by-sa/3.0/ 计算所有质数的简单而优雅的方法是这样的，但这种方式很慢，并且对于更高的数字，内存成本要高得多，因为使用了阶乘（!）函数...但它展示了Wilson定理的变化，以在Python中实现的算法生成所有质数。

#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
    if f%p%2:
        print p
    p+=1
    f*=(p-2)

- Steffen Wittum

Answer 8

这是一个使用C#实现的埃拉托色尼筛法：

    IEnumerable<int> GeneratePrimes(int n)
    {
        var values = new Numbers[n];

        values[0] = Numbers.Prime;
        values[1] = Numbers.Prime;

        for (int outer = 2; outer != -1; outer = FirstUnset(values, outer))
        {
            values[outer] = Numbers.Prime;

            for (int inner = outer * 2; inner < values.Length; inner += outer)
                values[inner] = Numbers.Composite;
        }

        for (int i = 2; i < values.Length; i++)
        {
            if (values[i] == Numbers.Prime)
                yield return i;
        }
    }

    int FirstUnset(Numbers[] values, int last)
    {
        for (int i = last; i < values.Length; i++)
            if (values[i] == Numbers.Unset)
                return i;

        return -1;
    }

    enum Numbers
    {
        Unset,
        Prime,
        Composite
    }

- Alon Gubkin

---

我会用 bool 而不是 enum 来完成这个。 - Letterman

Answer 9

我可以提供以下C#解决方案。它并不快，但非常清晰地说明了它所做的事情。

public static List<Int32> GetPrimes(Int32 limit)
{
    List<Int32> primes = new List<Int32>() { 2 };

    for (int n = 3; n <= limit; n += 2)
    {
        Int32 sqrt = (Int32)Math.Sqrt(n);

        if (primes.TakeWhile(p => p <= sqrt).All(p => n % p != 0))
        {
            primes.Add(n);
        }
    }

    return primes;
}

我忽略了任何检查 - 如果限制为负数或小于二（目前该方法将始终返回两个作为素数）。但这很容易修复。

更新

使用以下两个扩展方法：

public static void Do<T>(this IEnumerable<T> collection, Action<T> action)
{
    foreach (T item in collection)
    {
        action(item);
    }
}

public static IEnumerable<Int32> Range(Int32 start, Int32 end, Int32 step)
{
    for (int i = start; i < end; i += step)
    }
        yield return i;
    }
}

您可以将其重写为以下内容。

public static List<Int32> GetPrimes(Int32 limit)
{
    List<Int32> primes = new List<Int32>() { 2 };

    Range(3, limit, 2)
        .Where(n => primes
            .TakeWhile(p => p <= Math.Sqrt(n))
            .All(p => n % p != 0))
        .Do(n => primes.Add(n));

    return primes;
}

虽然效率较低（因为平方根需要重新计算很多次），但代码更加简洁。可以重写代码以惰性枚举质数，但这会使代码变得冗杂。

- Daniel Brückner

---

我几乎可以确定，在启用优化编译时，JIT编译器会将平方根的计算优化掉。您需要通过检查生成的汇编代码来验证这一点（IL仅部分优化，并且远远不及JIT编译器执行的优化）。循环提升和其他微观优化的日子已经过去了。事实上，有时试图聪明地超越JIT可能会减慢您的代码。 - Dave Black

Answer 10

使用一个质数生成器创建primes.txt文件，然后执行以下操作：

class Program
{
    static void Main(string[] args)
    {
        using (StreamReader reader = new StreamReader("primes.txt"))
        {
            foreach (var prime in GetPrimes(10, reader))
            {
                Console.WriteLine(prime);
            }
        }
    }

    public static IEnumerable<short> GetPrimes(short upTo, StreamReader reader)
    {
        int count = 0;
        string line = string.Empty;
        while ((line = reader.ReadLine()) != null && count++ < upTo)
        {
            yield return short.Parse(line);
        }
    }
}

在这个例子中，我在方法签名中使用了Int16，因此我的primes.txt文件包含从0到32767的数字。如果你想将其扩展为Int32或Int64，则primes.txt文件可能会显著变大。

- Darin Dimitrov

---

引用原帖：“我不介意使用哪种方法（朴素、筛法或其他任何方法），但我希望它相当简短且很明显如何工作。” 我认为我的答案完全相关。它也是最快的方法。 - Darin Dimitrov

即使他说“我不介意使用哪种方法……”，我认为这并不包括“列出质数清单”的方法。这就像回答“如何建造计算机”的问题时用“购买计算机”来回答一样。-1 - stevenvh

如果你在源代码中直接写出质数，而不是从文件中读取它们，那么速度会更快。 - Daniel Daranas

占用的内存很多吗？比将所有素数列表作为文本读入内存还多吗？你知道在.NET中字符串是如何工作的吗？ - jmservera

质数列表是一个无限但不可变的列表，因此使用预先计算的列表直到应用程序的可能上限是非常合理的。为什么要浪费时间编写可能有错误的代码，当有一个正确的公共列表可用于满足要求时呢？ - AndyM