c++ - 找到素数最快的算法是什么？

Question

哪个是使用 C++ 找出素数的最快算法？我已经使用了筛子的算法，但我仍然希望它更快！

score 92 · Accepted Answer

阿特金筛法的一个非常快速的实现是丹伯恩斯坦的素数。这种筛子比Eratosthenes筛子更有效。他的页面有一些基准信息。

score 33 · Accepted Answer

如果它必须非常快，您可以包含一个素数列表：http:
//www.bigprimes.net/archive/prime/

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

score 26 · Accepted Answer

他，他我知道我是一个回答老问题的死灵法师，但我刚刚发现这个问题正在网上搜索实现有效素数测试的方法。

到目前为止，我认为最快的素数测试算法是强概率素数（SPRP）。我从 Nvidia CUDA 论坛引用：

数论中更实际的利基问题之一与素数的识别有关。给定 N，你如何有效地确定它是否是素数？这不仅仅是一个理论问题，它可能是代码中真正需要的问题，也许当您需要在特定范围内动态查找素数哈希表大小时。如果 N 大约是 2^30，你真的要进行 30000 次除法测试来搜索任何因素吗？明显不是。

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

通过预先计算某些已知在 N 范围内总是成功的测试输入参数，可以将测试从概率拒绝变为确定的素数证明。不幸的是，这些“最知名的测试”的发现实际上是对一个巨大的 (实际上是无限的）域。1980 年，Carl Pomerance 创建了第一个有用测试列表（以他的 Quadratic Seive 算法对 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 测试来验证 Mersenne 素数。梅森素数的形式为 2^p -1。我认为 Lucas-Lehmer 检验是为梅森素数发现的最快算法。

如果你不仅想使用最快的算法，还想使用最快的硬件，尝试使用 Nvidia CUDA 来实现它，为 CUDA 编写一个内核并在 GPU 上运行它。

如果您发现足够大的素数，您甚至可以赚到一些钱，EFF 的奖金从 5 万美元到 25 万美元不等： https ://www.eff.org/awards/coop

score 18 · Accepted Answer

有一个 100% 的数学测试将检查一个数字P是素数还是合数，称为AKS Primality Test。

概念很简单：给定一个数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，因此这个数是素数。

和示例 where 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并测试剩余部分。

score 6 · Accepted Answer

你的问题是决定一个特定的数字是否是素数吗？然后你需要一个素数测试（简单）。或者你需要给定数字的所有素数吗？在这种情况下，初筛很好（容易，但需要记忆）。或者你需要一个数字的质因数吗？这将需要分解（如果您真的想要最有效的方法，则很难处理大量数据）。您正在查看的数字有多大？16位？32位？大？

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

score 2 · Accepted Answer

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

您是否只需要一些数字是否为素数的信息，您是否需要所有素数达到一定限制，或者您是否需要（可能）所有素数？
您必须处理的数字有多大？

对于超过一定大小的数字（我相信大约几百万），米勒拉宾和模拟测试只比筛子快。在此之下，使用试除法（如果您只有几个数字）或筛子会更快。

score 1 · Accepted Answer

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

Rabin Miller有一个非概率（确定性）变体。

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

score 0 · Accepted Answer

这是我一直在玩弄的 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 秒。

欢迎提出建议！

score 0 · Accepted Answer

我最近编写了这段代码来查找数字的总和。可以轻松修改它以查找数字是否为素数。基准在代码之上。

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

score 0 · Accepted Answer

我会让你决定它是否是最快的。

using System;
namespace PrimeNumbers
{

public static class Program
{
    static int primesCount = 0;


    public static void Main()
    {
        DateTime startingTime = DateTime.Now;

        RangePrime(1,1000000);   

        DateTime endingTime = DateTime.Now;

        TimeSpan span = endingTime - startingTime;

        Console.WriteLine("span = {0}", span.TotalSeconds);

    }


    public static void RangePrime(int start, int end)
    {
        for (int i = start; i != end+1; i++)
        {
            bool isPrime = IsPrime(i);
            if(isPrime)
            {
                primesCount++;
                Console.WriteLine("number = {0}", i);
            }
        }
        Console.WriteLine("primes count = {0}",primesCount);
    }



    public static bool IsPrime(int ToCheck)
    {

        if (ToCheck == 2) return true;
        if (ToCheck < 2) return false;


        if (IsOdd(ToCheck))
        {
            for (int i = 3; i <= (ToCheck / 3); i += 2)
            {
                if (ToCheck % i == 0) return false;
            }
            return true;
        }
        else return false; // even numbers(excluding 2) are composite
    }

    public static bool IsOdd(int ToCheck)
    {
        return ((ToCheck % 2 != 0) ? true : false);
    }
}
}

在配备 2.40 GHz 处理器的 Core 2 Duo 笔记本电脑上，查找和打印 1 到 1,000,000 范围内的质数大约需要82 秒。它发现了 78,498 个素数。

score 0 · Accepted Answer

我发现这个解决方案非常快，但它带来了后果，所以这被称为费马小定理。如果我们取任何数字p并将其放入(1^p)-1or (2^p)-2...(n^p)-n同样，并且我们得到的数字可以被整除，p那么它就是质数。谈论后果，这不是 100% 正确的解决方案。有一些像341(not prime) 这样的数字会通过测试(2^341)-2但在上失败(3^341)-3，所以它被称为合数。我们可以进行两项或多项检查，以确保他们通过所有检查。还有一种不是素数但也通过了所有测试用例的数字：（561、1729 Ramanujan Taxi no等。

好消息：(2^p)-2在前 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;
}

score 0 · Accepted Answer

我今天用 C 语言编写了它，用 tcc 编译，几年前在准备竞争性考试时发现。不知道有没有人已经写过。它真的很快（但你应该决定它是否很快）。在平均 32% 的 CPU 使用率的 i7 处理器上，花了一两分钟的时间在 10 到 1,00,00,000 之间找出大约 1,00,004 个素数。如您所知，只有最后一位数字为 1、3、7 或 9 的数字才能是素数，并且要检查该数字是否为素数，您必须将该数字除以先前找到的素数。所以首先取一组四个数字 = {1,3,7,9}，通过除以已知素数来测试它，如果提示非零则数字是素数，将其添加到素数数组。然后将 10 添加到组中，使其变为 {11,13,17,19} 并重复该过程。

#include <stdio.h>
int main() {    
    int nums[4]={1,3,7,9};
    int primes[100000];
    primes[0]=2;
    primes[1]=3;
    primes[2]=5;
    primes[3]=7;
    int found = 4;
    int got = 1;
    int m=0;
    int upto = 1000000;
    for(int i=0;i<upto;i++){
        //printf("iteration number: %d\n",i);
        for(int j=0;j<4;j++){
            m = nums[j]+10;
            //printf("m = %d\n",m);
            nums[j] = m;
            got = 1;
            for(int k=0;k<found;k++){
                //printf("testing with %d\n",primes[k]);
                if(m%primes[k]==0){
                    got = 0;
                    //printf("%d failed for %d\n",m,primes[k]);
                    break;
                }
            }
            if(got==1){
                //printf("got new prime: %d\n",m);
                primes[found]= m;
                found++;
            }
        }
    }
    printf("found total %d prime numbers between 1 and %d",found,upto*10);
    return 0;
}

score -1 · Accepted Answer

寻找因素的解决方案：

def divisors(integer):
    result = set()
    i = 2
    j = integer/2
    while(i <= j):
        if integer % i == 0:
            result.add(i)
            #it dont need to 
            result.add(integer//i)
        i += 1
        j = integer//i
    if len(result) > 0:
        return f"not  prime {sorted(result)}"
    else:
        return f"{integer} is prime"

--- 测试 ---- 导入时间

start_time = time.time()
print(divisors(180180180180))
print("--- %s seconds ---" % (time.time() - start_time))

--- 0.06314539909362793 秒 ---

start_time = time.time()
print(divs(180180180180180))
print("--- %s seconds ---" % (time.time() - start_time))

--- 1.5997519493103027 秒 ---

start_time = time.time()
print(divisors(1827))
print("--- %s seconds ---" % (time.time() - start_time))

--- 0.0 秒 ---

start_time = time.time()
print(divisors(104729))
print("--- %s seconds ---" % (time.time() - start_time))

--- 0.0 秒 ---

使用此代码：

def divs(integer):
    result = set()
    i = 2
    j = integer / 2
    loops = 0
    while (i <= j):
        if integer % i == 0:
            print(f"loops:{loops}")
            return f"{integer} is not a prime"
        i += 1
        j = integer // i
        loops += 1
    print(f"loops:{loops}")
    
    return f"{integer} is prime"

--- 测试 ---

start_time = time.time()
print(divs(180180180180180180180180))
print("--- %s seconds ---" % (time.time() - start_time))

--- 0.0 秒 ---

score -2 · Accepted Answer

我总是使用这种方法来计算使用筛算法的素数。

void primelist()
 {
   for(int i = 4; i < pr; i += 2) mark[ i ] = false;
   for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
   for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
       if(mark[ i ])
          for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
  prime[ 0 ] = 2; ind = 1;
  for(int i = 3; i < pr; i += 2)
    if(mark[ i ]) ind++; printf("%d\n", ind);
 }

score -3 · Accepted Answer

#include<stdio.h>
main()
{
    long long unsigned x,y,b,z,e,r,c;
    scanf("%llu",&x);
    if(x<2)return 0;
    scanf("%llu",&y);
    if(y<x)return 0;
    if(x==2)printf("|2");
    if(x%2==0)x+=1;
    if(y%2==0)y-=1;
    for(b=x;b<=y;b+=2)
    {
        z=b;e=0;
        for(c=2;c*c<=z;c++)
        {
            if(z%c==0)e++;
            if(e>0)z=3;
        }
        if(e==0)
        {
            printf("|%llu",z);
            r+=1;
        }
    }
    printf("|\n%llu outputs...\n",r);
    scanf("%llu",&r);
}

score -4 · Accepted Answer

我知道有点晚了，但这可能对通过搜索到达这里的人有用。无论如何，这里有一些 JavaScript 依赖于只需要测试素数的事实，因此代码生成的早期素数被重新用作以后的测试因子。当然，首先过滤掉所有偶数和 mod 5 值。结果将在数组 P 中，并且此代码可以在 i7 PC 上在 1.5 秒内处理 1000 万个素数（或大约 20 秒内处理 1 亿个）。用C重写它应该非常快。

var P = [1, 2], j, k, l = 3

for (k = 3 ; k < 10000000 ; k += 2)
{
  loop: if (++l < 5)
  {
    for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
      if (k % P[j] == 0) break loop

    P[P.length] = k
  }
  else l = 0
}

score -4 · Accepted Answer

#include <iostream>

using namespace std;

int set [1000000];

int main (){

    for (int i=0; i<1000000; i++){
        set [i] = 0;
    }
    int set_size= 1000;
    set [set_size];
    set [0] = 2;
    set [1] = 3;
    int Ps = 0;
    int last = 2;

    cout << 2 << " " << 3 << " ";

    for (int n=1; n<10000; n++){
        int t = 0;
        Ps = (n%2)+1+(3*n);
        for (int i=0; i==i; i++){
            if (set [i] == 0) break;
            if (Ps%set[i]==0){
                t=1;
                break;
            }
        }
        if (t==0){
            cout << Ps << " ";
            set [last] = Ps;
            last++;
        }
    }
    //cout << last << endl;


    cout << endl;

    system ("pause");
    return 0;
}

score -12 · Accepted Answer

#include<iostream>
using namespace std;

void main()
{
    int num,i,j,prime;
    cout<<"Enter the upper limit :";
    cin>>num;

    cout<<"Prime numbers till "<<num<<" are :2, ";

    for(i=3;i<=num;i++)
    {
        prime=1;
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
                prime=0;
                break;
            }
        }

        if(prime==1)
            cout<<i<<", ";

    }
}

c++ - 找到素数最快的算法是什么？

18 回答 18

Related

Reference