生成素数的最优雅方式 [闭合]

algorithm java c# primes

2022-08-31 11:45:24

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

ArrayList generatePrimes(int n)

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

我知道如何编写这个函数，但是当我昨晚这样做时，它并没有像我希望的那样好。以下是我想出的：

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）
埃拉托斯特尼筛子（星蓝）的非常干净的实现
使用Java和非常简单的代码，尽管我无法想象它特别高效（dfa）BigIntegernextProbablePrime
使用 LINQ 懒惰地生成素数列表（Maghis）
在文本文件中放入大量素数，并在必要时读取它们（darin）

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

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

答案 2

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

Standard Method （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]

埃拉托斯特尼筛（星蓝）)

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

孙达拉姆的筛子

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