最优雅的生成素数的方法 [英] Most elegant way to generate prime numbers

问题描述

实现这个功能最优雅的方式是什么:

What is the most elegant way to implement this function:

ArrayList generatePrimes(int n)

此函数生成前 n 个素数(where n>1)，所以 generatePrimes(5) 将返回一个 ArrayList 和 {2, 3, 5, 7, 11}.(我正在 C# 中进行此操作，但我对 Java 实现感到满意 - 或任何其他类似的语言(因此不是 Haskell)).

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.

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

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:

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

• 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 nextProbablePrime for 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:我已经用 C# 实现 这里给出的几个方法，以及这里没有提到的另一个方法.他们都有效地找到了第一个 n 素数(我有一个 找到提供给筛子的极限的体面方法).

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).

推荐答案

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

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 :-)

标准方法(PeterSmit、jmservera、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.

埃拉托色尼筛网(星蓝)

这会找到 k 的所有质数.要列出前 n 个素数，我们首先需要近似第 n 个素数的值.下面的方法，如此处所述，这样做.

This finds all the primes to k. To make a list of the first n primes, we first need to approximate value of the nth 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;
}

Sundaram 筛网

我最近才发现这个筛网，但它可以非常简单地实现.我的实现没有 Eratosthenes 的筛子那么快，但比朴素的方法要快得多.

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屋！