C# 最优雅的生成素数的方法

Most elegant way to generate prime numbers

提问by David Johnstone

What is the most elegant way to implement this function:

实现此功能的最优雅的方法是什么：

ArrayList generatePrimes(int n)

This function generates the first nprimes (edit: where n>1), so generatePrimes(5)will return an ArrayListwith {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)).

此函数生成第一个n素数（编辑： where n>1），因此generatePrimes(5)将返回ArrayListwith {2, 3, 5, 7, 11}。（我在 C# 中这样做，但我对 Java 实现感到满意 - 或任何其他类似的语言（所以不是 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.

我不太关心速度，虽然我不希望它明显效率低下。我不介意使用哪种方法（天真或筛分或其他任何方法），但我确实希望它相当简短且显而易见它是如何工作的。

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:

编辑：感谢所有回复的人，尽管许多人没有回答我的实际问题。重申一下，我想要一段漂亮干净的代码来生成素数列表。我已经知道如何以多种不同的方式来完成它，但是我倾向于编写不太清楚的代码。在此线程中，提出了一些不错的选择：

• 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 and nextProbablePrimefor 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)

• 我最初拥有的更好的版本（Peter Smit、jmservera 和 Rekreativc）
• Eratosthenes (starblue) 筛子的一个非常干净的实现
• 使用 Java 的BigIntegers 和nextProbablePrime非常简单的代码，虽然我无法想象它特别有效（dfa）
• 使用 LINQ 懒惰生成素数列表 (Maggis)
• 将大量素数放在一个文本文件中，并在必要时读取它们（darin）

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 nprimes effectively (and I have a decent methodof finding the limit to provide to the sieves).

编辑 2：我已经在 C# 中实现了这里给出的几个方法，以及这里没有提到的另一个方法。他们都有效地找到了前n 个素数（我有一个不错的方法来找到提供给筛子的极限）。

采纳答案by David Johnstone

Many thanks to all who gave helpful answers. Here are my implementations of a few different methods of finding the first nprimes 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 :-)

非常感谢所有提供有用答案的人。这是我在 C#中找到前n 个素数的几种不同方法的实现。前两种方法几乎是这里发布的。（海报名称在标题旁边。）我计划在某个时候做 Atkin 的筛选，尽管我怀疑它不会像目前这里的方法那么简单。如果有人能看到任何改进这些方法的方法，我很想知道:-)

Standard Method(Peter Smit, jmservera, Rekreativc)

标准方法（彼得·斯密特，jmservera，Rekreativc）

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.

第一个素数是 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;
}

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.

这已经通过仅测试被测试数字的平方根的可分性进行了优化；并且只测试奇数。这可以通过仅测试形式的数字来进一步优化6k+[1, 5]，或30k+[1, 7, 11, 13, 17, 19, 23, 29]或等等。

Sieve of Eratosthenes(starblue)

埃拉托色尼筛（星蓝）

This finds all the primes to k. To make a list of the first nprimes, we first need to approximate value of the nth prime. The following method, as described here, does this.

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

Sieve of Sundaram

Sundaram 的筛子

I only discovered this sieverecently, 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.

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

回答by David Bo?jak

This is the most elegant I can think of on short notice.

这是我能在短时间内想到的最优雅的。

ArrayList generatePrimes(int numberToGenerate)
{
    ArrayList rez = new ArrayList();

    rez.Add(2);
    rez.Add(3);

    for(int i = 5; rez.Count <= numberToGenerate; i+=2)
    {
        bool prime = true;
        for (int j = 2; j < Math.Sqrt(i); j++)
        {
            if (i % j == 0)
            {
                    prime = false;
                    break;
            }
        }
        if (prime) rez.Add(i);
    }

    return rez;
}

Hope this helps to give you an idea. I'm sure this can be optimised, however it should give you an idea how your version could be made more elegant.

希望这有助于给你一个想法。我相信这可以优化，但是它应该让您了解如何使您的版本更优雅。

EDIT:As noted in the comments this algorithm indeed returns wrong values for numberToGenerate < 2. I just want to point out, that I wasn't trying to post him a great method to generate prime numbers (look at Henri's answer for that), I was mearly pointing out how his method could be made more elegant.

编辑：正如评论中所指出的，该算法确实为 numberToGenerate < 2 返回了错误的值。我只想指出，我并没有试图向他发布一个生成素数的好方法（看看 Henri 的答案），我只是在指出如何使他的方法更加优雅。

回答by Darin Dimitrov

Use a prime numbers generatorto create primes.txt and then:

使用素数生成器创建 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);
        }
    }
}

In this case I use Int16 in the method signature, so my primes.txt file contains numbers from 0 to 32767. If you want to extend this to Int32 or Int64 your primes.txt could be significantly larger.

在这种情况下，我在方法签名中使用 Int16，因此我的 primes.txt 文件包含从 0 到 32767 的数字。如果您想将其扩展到 Int32 或 Int64，您的 primes.txt 可能要大得多。

回答by cjk

To make it more elegant, you should refactor out your IsPrime test into a separate method, and handle the looping and increments outside of that.

为了使它更优雅，您应该将 IsPrime 测试重构为一个单独的方法，并在此之外处理循环和增量。

回答by jmservera

Using your same algorithm you can do it a bit shorter:

使用相同的算法，您可以将其缩短一点：

List<int> primes=new List<int>(new int[]{2,3});
for (int n = 5; primes.Count< numberToGenerate; n+=2)
{
  bool isPrime = true;
  foreach (int prime in primes)
  {
    if (n % prime == 0)
    {
      isPrime = false;
      break;
    }
  }
  if (isPrime)
    primes.Add(n);
}

回答by dfa

you should take a look at probable primes. In particular take a look to Randomized Algorithmsand Miller–Rabin primality test.

你应该看看probable primes。特别是看看随机算法和米勒-拉宾素性检验。

For the sake of completeness you could just use java.math.BigInteger:

为了完整起见，您可以只使用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);
    }
}

回答by Peter Smit

You are on the good path.

你在好的道路上。

Some comments

一些评论

• primes.Add(3); makes that this function doesn't work for number = 1

• You dont't have to test the division with primenumbers bigger that the squareroot of the number to be tested.

• 素数.Add(3); 使此功能不适用于 number = 1

• 您不必使用比要测试的数字的平方根大的素数来测试除法。

Suggested code:

建议代码：

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

回答by Vincent Robert

I did it in Java using a functional library I wrote, but since my library uses the same concepts as Enumerations, I am sure the code is adaptable:

我使用我编写的函数库在 Java 中完成了它，但由于我的库使用与 Enumerations 相同的概念，我确信代码具有适应性：

Iterable<Integer> numbers = new Range(1, 100);
Iterable<Integer> primes = numbers.inject(numbers, new Functions.Injecter<Iterable<Integer>, Integer>()
{
    public Iterable<Integer> call(Iterable<Integer> numbers, final Integer number) throws Exception
    {
        // We don't test for 1 which is implicit
        if ( number <= 1 )
        {
            return numbers;
        }
        // Only keep in numbers those that do not divide by number
        return numbers.reject(new Functions.Predicate1<Integer>()
        {
            public Boolean call(Integer n) throws Exception
            {
                return n > number && n % number == 0;
            }
        });
    }
});

回答by stevenvh

The simplest method is the trial and error: you try if any number between 2 and n-1 divides your candidate prime n.
First shortcuts are of course a)you only have to check odd numbers, and b)you only hav to check for dividers up to sqrt(n).

最简单的方法是试错法：如果 2 到 n-1 之间的任何数除以候选素数 n，您就尝试。
第一个快捷方式当然是 a) 你只需要检查奇数，b) 你只需要检查直到 sqrt(n) 的除法器。

In your case, where you generate all previous primes in the process as well, you only have to check if any of the primes in your list, up to sqrt(n), divides n.
Should be the fastest you can get for your money :-)

在您的情况下，您也在该过程中生成所有先前的素数，您只需检查列表中的任何素数，直到 sqrt(n)，是否除以 n。
应该是你能以最快的速度获得的:-)

edit
Ok, code, you asked for it. But I'm warning you :-), this is 5-minutes-quick-and-dirty Delphi code:

编辑
好的，代码，你要求它。但我要警告你 :-)，这是 5 分钟又快又脏的 Delphi 代码：

procedure TForm1.Button1Click(Sender: TObject);
const
  N = 100;
var
  PrimeList: TList;
  I, J, SqrtP: Integer;
  Divides: Boolean;
begin
  PrimeList := TList.Create;
  for I := 2 to N do begin
    SqrtP := Ceil(Sqrt(I));
    J := 0;
    Divides := False;
    while (not Divides) and (J < PrimeList.Count) 
                        and (Integer(PrimeList[J]) <= SqrtP) do begin
      Divides := ( I mod Integer(PrimeList[J]) = 0 );
      inc(J);
    end;
    if not Divides then
      PrimeList.Add(Pointer(I));
  end;
  // display results
  for I := 0 to PrimeList.Count - 1 do
    ListBox1.Items.Add(IntToStr(Integer(PrimeList[I])));
  PrimeList.Free;
end;

回答by grom

Here is a python code example that prints out the sum of all primes below two million:

这是一个 python 代码示例，它打印出低于 200 万的所有素数的总和：

from math import *

limit = 2000000
sievebound = (limit - 1) / 2
# sieve only odd numbers to save memory
# the ith element corresponds to the odd number 2*i+1
sieve = [False for n in xrange(1, sievebound + 1)]
crosslimit = (int(ceil(sqrt(limit))) - 1) / 2
for i in xrange(1, crosslimit):
    if not sieve[i]:
        # if p == 2*i + 1, then
        #   p**2 == 4*(i**2) + 4*i + 1
        #        == 2*i * (i + 1)
        for j in xrange(2*i * (i + 1), sievebound, 2*i + 1):
            sieve[j] = True
sum = 2
for i in xrange(1, sievebound):
    if not sieve[i]:
        sum = sum + (2*i+1)
print sum

回答by grom

I know you asked for non-Haskell solution but I am including this here as it relates to the question and also Haskell is beautiful for this type of thing.

我知道您要求非 Haskell 解决方案，但我将其包含在此处，因为它与问题有关，而且 Haskell 对这类事情很漂亮。

module Prime where

primes :: [Integer]
primes = 2:3:primes'
  where
    -- Every prime number other than 2 and 3 must be of the form 6k + 1 or 
    -- 6k + 5. Note we exclude 1 from the candidates and mark the next one as
    -- prime (6*0+5 == 5) to start the recursion.
    1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n      = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p    = n `mod` p == 0