哪个是查找质数最快的算法？

Question

使用C++查找质数的最快算法是什么？我已经使用了筛法，但我仍希望它更快！

- kasperasky

---

@Jaider 这个方法在数字低至7（111）时就失效了。对于1001=9，它也是无效的。而且显然对于几乎所有的质数都是无效的（不包括形式为111...1的梅森素数——经典生成的例子——即2^p - 1的情况）。 - Daniel Kats

@Kasperasky - 你没有提到是哪个筛法？你可能指的是Eranthoses筛法！ - user2618142

当问题无法回答而不知道要涵盖的数字范围时，看到答案数量令人惊讶。如果您想要所有质数，则不需要快速算法。 - user1196549

@WillNess：int p[] = {2, 3}; 是否可以被认为是“最快的质数查找算法”？ - user1196549

@WillNess：我一直在想，一个质数是否足以满足“numberS”。 - user1196549

Answer 1

丹·伯恩斯坦的 primegen 实现了一个非常快速的 Atkin筛法，比 Eratosthenes筛法 更高效。他的网页上提供了一些基准信息。

- Greg Hewgill

---

实际上，我不认为primegen是最快的，甚至不是前两个最快的；我认为yafu和primesieve通常都更快，特别是在超过2^32的情况下。两者都采用了修改后的埃拉托斯特尼筛法，而不是阿特金-伯恩斯坦筛法。 - Charles

Primesieve是一个使用Eratosthenes筛法的库，是最快的算法之一。相比于Atkin筛法（SoA），Primesieve可以减少操作次数，并且总是更快的。在32位数字范围内(2^32 - 1)，Primesieve大约进行了12亿次筛选，而SoA则需要进行约14亿次组合的开关和无平方因子的操作，这两种操作的复杂度相当，并且可以以类似的方式进行优化。 - GordonBGood

续前文：Bernstein只使用与SoA相同的有效轮分解来比较SoE，该分解为2;3;5轮，使用该轮会在32位数字范围内产生约18.3亿次筛查；当对等其他优化进行比较时，这使得SoA大约快30% 仅在比较此限制版本的SoE时。然而，primesieve算法结合了2;3;5;7轮和2;3;5;7;11;13;17轮段预筛选，将操作次数降低到约12亿次，比等效操作循环优化下的SoA快约16.7%。 - GordonBGood

SoA算法中的高因子轮分解并不能使很大的差别，因为2；3；5因子分解轮是该算法的一个固有部分。 - GordonBGood

@Eamon Nerbonne，WP是正确的。然而，仅仅拥有略微更好的计算复杂度并不能使算法在一般用途中运行得更快。在这些评论中，我指的是埃拉托色尼筛法（SoE）的最大轮因数分解（这对于阿特金筛法（SoA）是不可能的），它使得SoE在约十亿的范围内进行较少的操作。在超过这个点之后，一般需要使用页面划分来克服内存限制，而这就是SoA失败的地方，随着范围的增加，所需的固定开销将呈迅速增长趋势。 - GordonBGood

Answer 2

如果需要非常快的速度，您可以包含一个质数列表：
http://www.bigprimes.net/archive/prime/

如果您只想知道某个数字是否为质数，可以在维基百科上列出各种素性测试。它们可能是确定大数字是否为质数的最快方法，尤其是因为它们可以告诉您一个数字不是质数。

- gs

---

所有质数的列表？我认为你想要的是前几个质数的列表... :) - j_random_hacker

如果您认为一亿不算多的话，那好的 :) - Georg Schölly

相对于无穷大来说，一亿绝对是“几个”了 ;) - Timofey

你认为为什么阿特金筛法（SoA）比埃拉托色尼筛法（SoE）更快？当你只是按照你提供的维基百科文章中的伪代码实现程序时，事实上并不是这样。如果使用与SoA相似的优化水平来实现SoE，则在非常大的筛选范围内，SoA的操作稍微少一些，但是这种计算复杂性的增加的额外常数因子开销通常会抵消这种优势，所以在实际应用中，SoE更好。请注意，本文不包括解释。 - GordonBGood

质数的好处在于它们不会改变。一旦你有了一个列表，你可以永远重复使用它。 - Mark Ransom

Answer 3

到目前为止，我相信最快的质数测试算法是强似素数（SPRP）算法。我引用了Nvidia CUDA论坛上的话：

数论中更实际的细分问题之一涉及素数的识别。给定N，如何有效地确定它是否为素数？这不仅是一个理论问题，在编码时可能需要真正解决，也许当您需要在某些范围内动态查找素数哈希表大小时。如果N大约为2^30，您真的想做30000个除法测试来搜索任何因子吗？显然不行。

这个问题的常见实际解决方案是称为欧拉概率素数测试的简单测试，以及更强大的一般化称为强概率素数（SPRP）。这是一种测试，对于整数N可以概率上将其分类为素数或非素数，并且重复测试可以增加正确性概率。测试本身的缓慢部分主要涉及计算类似于A^(N-1)模N的值。任何实现RSA公钥加密变体的人都使用了此算法。它对于巨大的整数（例如512位）以及普通的32位或64位整数都很有用。

该测试可以从概率拒绝更改为素性的明确证明，方法是预先计算某些已知始终成功的测试输入参数，适用于N的范围。不幸的是，发现这些“最佳已知测试”的过程实际上是对一个巨大（事实上是无限）的域进行搜索。 1980年，Carl Pomerance（以他的二次筛法算法因素分解RSA-129而闻名）创建了第一个有用测试列表。之后，Jaeschke在1993年显着改进了结果。 2004年，Zhang和Tang改进了搜索域的理论和限制。Greathouse和Livingstone发布了迄今为止在网上的最新结果，位于http://math.crg4.com/primes.html，是对巨大搜索域的最佳结果。

更多信息请参见： http://primes.utm.edu/prove/prove2_3.html 和 http://forums.nvidia.com/index.php?showtopic=70483

如果您只需要一种生成非常大的质数的方法，并且不关心生成所有小于整数n的质数，那么可以使用Lucas-Lehmer测试来验证梅森素数。梅森素数是2^p -1的形式。我认为Lucas-Lehmer测试是发现梅森素数最快的算法。

如果您不仅想使用最快的算法，而且还想使用最快的硬件，请尝试使用Nvidia CUDA实现它，编写CUDA内核并在GPU上运行它。

如果您发现足够大的质数，甚至可以赚取一些奖金，EFF提供从50K美元到250K美元的奖励： https://www.eff.org/awards/coop

- Mack

Answer 4

有一种100%的数学测试可以检查一个数字P是质数还是合数，它被称为AKS素性测试。

这个概念很简单：给定一个数P，如果(x-1)^P - (x^P-1)的所有系数都能被P整除，则P是一个质数，否则它是一个合数。

例如，给定P=3，将得到多项式：

   (x-1)^3 - (x^3 - 1)
 = x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
 = 3x^2 - 3x

系数都可以被3整除，因此这个数是质数。

当P = 4时，它不是一个质数的例子如下：

   (x-1)^4 - (x^4-1)
 = x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
 = -4x^3 + 6x^2 - 4x

在这里，我们可以看到系数6不是4的倍数，因此它不是质数。

多项式(x-1)^P将有P+1项，并且可以使用组合找到。因此，此测试将在O(n)运行时间内运行，因此我不知道这会有多大用处，因为您可以简单地迭代i从0到p并测试余数。

- Kousha

---

AKS在实践中非常缓慢，与其他已知方法相比不具竞争力。你所描述的方法不是AKS算法，而是一个比未经优化的试除法更慢的引理（正如你所指出的那样）。 - DanaJ

你好 @Kousha，x 在 (x-1)^P - (x^P-1) 中代表什么？你有这方面的示例代码吗？用 C++ 写一个判断整数是否为质数的程序。 - kiLLua

@kiLLua X只是一个变量。决定数字是否为质数的是X的系数。我没有代码。我不建议实际使用这种方法来确定一个数字是否为质数。这只是质数的一个非常酷的数学行为，但除此之外它非常低效。 - Kousha

Answer 5

你是否需要判断一个数字是否为质数？那么你需要使用质性测试（简单）。或者你需要找出给定数字以下的所有质数？这种情况下，质数筛选法是很好的选择（简单，但需要内存）。或者你需要一个数字的质因数？这将需要进行因式分解（如果你真的想要最有效的方法，则对于大数字来说比较困难）。你所处理的数字有多大？16位？32位？更大吗？

一个聪明而高效的方法是预先计算质数表并使用位级编码将它们保存在文件中。该文件被视为一个长的位向量，其中位n表示整数n。如果n是质数，则将其位设置为1，否则设置为0。查找非常快速（你可以计算字节偏移和位掩码），不需要将文件加载到内存中。

- Christian Lindig

---

一个好的素性测试应该与主存延迟相竞争，适用于可以合理放置的素数表，因此除非它可以适应L2，否则我不会使用它。 - Charles

Answer 6

Rabin-Miller 是一种标准的概率素性测试。您运行它 K 次，输入数字要么绝对是合成数，要么是可能是质数，错误概率为 4^-K。（进行几百次迭代，它几乎肯定会告诉您真相）

还有一种非概率（确定性）Rabin Miller 的变体。

Great Internet Mersenne Prime Search（GIMPS）已经发现了世界上最大的素数记录（截至2017年6月为2^74,207,281 - 1），使用几种算法，但这些都是特殊形式的素数。然而，上述GIMPS页面确实包括一些一般的确定性素性测试。它们似乎表明，“最快”的算法取决于要测试的数字的大小。如果您的数字适合64位，则可能不应使用旨在处理数百万位数的质数的方法。

- Jason S

Answer 7

这取决于你的应用程序。有一些考虑因素：

• 你只需要知道几个数字是否是质数，还是需要所有小于某个限制的质数，或者你需要（可能）所有的质数？
• 你要处理的数字有多大？

米勒-拉宾和类似的测试仅对大于某个大小的数字（大约在几百万左右）比筛法更快。在此之下，如果你只有几个数字，使用试除法；如果你需要所有的质数，则使用筛法更快。

- Harleqin

Answer 8

这是我一直在玩弄的Python Eratosthenes筛法实现。

def eratosthenes(maximum: int) -> list[int | None]:
    """
    Find all the prime numbers between 2 and `maximum`.

    Args:
        maximum: The maximum number to check.

    Returns:
        A list of primes between 2 and `maximum`.
    """

    if maximum < 2:
        return []

    # Discard even numbers by default.
    sequence = dict.fromkeys(range(3, maximum+1, 2), True)

    for num, is_prime in sequence.items():
        # Already filtered, let's skip it.
        if not is_prime:
            continue

        # Avoid marking the same number twice.
        for num2 in range(num ** 2, maximum+1, num):
            # Here, `num2` might contain an even number - skip it.
            if num2 in sequence:
                sequence[num2] = False

    # Re-add 2 as prime and filter out the composite numbers.
    return [2] + [num for num, is_prime in sequence.items() if is_prime]

这段代码在一部普通的三星Galaxy A40手机上处理10000000个数字大约需要16秒。

欢迎提出建议！

- Death Mask Salesman

---

应该写成 -> list[int]。一个空的列表（你可能用 None 来引用）仍然是一个 int 的列表。 - matheburg

你最好用if num2 % 2:替换if num2 in sequence:。这样做会显著提高速度（而且我认为更易读）。 - matheburg

稍微快一点的版本：https://dev59.com/unRB5IYBdhLWcg3w9b19#73035195 - matheburg

Answer 9

我很快就找到了这个解决方案，但它有后果，所以这被称为费马小定理。如果我们取任何数字p并将其放入(1^p)-1或(2^p)-2... (n^p)-n等式中，得到的数字可被p整除，则它是一个质数。谈到后果，这不是100%正确的解决方案。有些数字（如341）（不是质数）将通过(2^341)-2测试，但在(3^341)-3测试中失败，因此它被称为合成数。我们可以进行两次或更多次检查，以确保它们全部通过。还有一种类型的数字既不是质数，也通过所有测试用例：（561、1729 Ramanujan出租车号等）。

引用：“好处是：在前250亿个数字中，只有2183个失败了这个情况。”

#include <iostream>
#include <math.h>
using namespace std;

int isPrime(int p)
{
    int tc = pow(2, p) - 2;
    if (tc % p == 0)
    {
        cout << p << "is Prime ";
    }
    else
    {
        cout << p << "is Not Prime";
    }
    return 0;
}

int main()
{
    int p;
    cin >> p;
    isPrime(p);
    return 0;
} 

- Adarsh Pawar

Answer 10

我最近编写了这段代码，用于计算数字的总和。它可以轻松修改，以查找一个数字是否为质数。基准测试数据在代码顶部。

// built on core-i2 e8400
// Benchmark from PowerShell
// Measure-Command { ExeName.exe }
// Days              : 0
// Hours             : 0
// Minutes           : 0
// Seconds           : 23
// Milliseconds      : 516
// Ticks             : 235162598
// TotalDays         : 0.00027217893287037
// TotalHours        : 0.00653229438888889
// TotalMinutes      : 0.391937663333333
// TotalSeconds      : 23.5162598
// TotalMilliseconds : 23516.2598
// built with latest MSVC
// cl /EHsc /std:c++latest main.cpp /O2 /fp:fast /Qpar

#include <cmath>
#include <iostream>
#include <vector>

inline auto prime = [](std::uint64_t I, std::vector<std::uint64_t> &cache) -> std::uint64_t {
    std::uint64_t root{static_cast<std::uint64_t>(std::sqrtl(I))};
    for (std::size_t i{}; cache[i] <= root; ++i)
        if (I % cache[i] == 0)
            return 0;

    cache.push_back(I);
    return I;
};

inline auto prime_sum = [](std::uint64_t S) -> std::uint64_t {
    std::uint64_t R{5};
    std::vector<std::uint64_t> cache;
    cache.reserve(S / 16);
    cache.push_back(3);

    for (std::uint64_t I{5}; I <= S; I += 8)
    {
        std::uint64_t U{I % 3};
        if (U != 0)
            R += prime(I, cache);
        if (U != 1)
            R += prime(I + 2, cache);
        if (U != 2)
            R += prime(I + 4, cache);
        R += prime(I + 6, cache);
    }
    return R;
};

int main()
{
    std::cout << prime_sum(63210123);
}

- Terens Tare