使用C ++找出质数最快的算法是哪一种?我已经使用了sieve的算法,但我仍然希望它更快!

评论

我发现了一篇老文章,但看起来很有趣:质数有趣

@Jaider对于低至7(111)的数字将失败。对于1001 = 9,它也会失败。显然,它对几乎所有的素数都无效(不包括2 ^ p-1,这是梅森素数-经典生成的示例-始终为111 ... 1的形式)

@Kasperasky-您没有提到哪个筛子?您可能是说Eranthoses筛子!

Eratosthenes算法筛网

#1 楼

丹·伯恩斯坦(Dan Bernstein)的primegen是阿特金筛网(Sieve of Atkin)的一个非常快速的实现。该筛子比Eratosthenes筛子更有效。他的页面上有一些基准信息。

评论


实际上,我不认为primegen是最快的,甚至不是第二快的。我认为,yafu和primesieve总体上都更快,并且肯定超过2 ^ 32。两者都是(改良的)Eratosthenes筛子,而不是Atkin-Bernstein筛子。

–查尔斯
2011年8月19日在4:29



Primeato的Eratosthenes筛(SoE)是可能的最快算法,并且总是比Atkin SoA的Sieve筛查的任何实现都要快,包括本答案中链接的Bernstein的筛查,因为与SoA相比,primesieve减少了操作数量:对于32-比特数范围(2 ^ 32-1),primeiseeve进行约12亿剔除,而SoA总共进行约14亿组合的切换和无平方运算,这两种操作具有大约相同的复杂度,并且可以在相同的程度上进行优化道路。

–GordonBGood
2013年12月6日下午3:06

续:伯恩斯坦只比较了SoE使用与SoA相同的有效转轮分解,即2; 3; 5转轮,使用该转轮会在32位数字范围内产生大约18.3亿剔除。当将此SoE受限版本与其他等效优化进行比较时,这会使SoA速度提高约30%。但是,primesieve算法将2; 3; 5; 7车轮与2; 3; 5; 7; 11; 13; 17车轮分段预剔除结合使用,以将操作次数减少到大约12亿次具有等效操作循环优化功能的SoA速度比SoA快16.7%。

–GordonBGood
2013年12月6日下午3:16

续2:SoA con没有较高的因子轮分解,因为2; 3; 5因子分解轮是算法的“嵌入”部分,因此差异不大。

–GordonBGood
2013年12月6日下午3:18

@Eamon Nerbonne,WP是正确的;但是,仅具有稍微更好的计算复杂性并不能使通用算法更快。在这些评论中,我指的是Eratosthenes筛(SoE)的最大车轮分解系数(对于Atkin-SoA筛子是不可能的)使SoE的运行次数略微减少,达到约十亿范围。远远超过这一点,通常需要使用页面分段来克服内存限制,那就是SoA失败的地方,随着范围的增加,固定开销的增加迅速增加。

–GordonBGood
2014年6月1日14:37

#2 楼

如果必须非常快,则可以包含素数列表:http://www.bigprimes.net/archive/prime/

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

评论


所有素数的清单?我认为您的意思是前几个素数的列表... :)

– j_random_hacker
09年1月18日在4:19

如果您给100000000打电话,那么可以。 :)

–乔治·舍利(GeorgSchölly)
09年1月18日在7:35

与无穷大相比,肯定100000000是“几个”;)

– Timofey
2012年1月21日在16:08

您为什么认为阿特金筛(SoA)快于Eratosthenes(SoE)筛?当您只是使用您链接的Wikipedia文章中的伪代码实现程序时,肯定不是。如果以与SoA相似的可能优化水平来实现SoE,则与SoE相比,针对SoA进行非常大的筛分范围时,操作会稍微少一些,但是通常,这种收益被增加的复杂性和这种计算复杂性的额外恒定因子开销,使得对于实际应用而言,SoE更好。

–GordonBGood
2014年3月20日在2:53

那是质数的优点,它们不变。有了列表后,您就可以永远重复使用它。

– Mark Ransom
12月19日4:06

#3 楼

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

直到现在,我相信最快的质数测试算法是强概率质数(SPRP)。我在Nvidia CUDA论坛上引用:


数论中较实际的利基问题之一与素数的确定有关。给定N,您如何有效地确定它是否为素数?这不仅是一个棘手的问题,而且可能是代码中真正需要的一个问题,也许当您需要动态地找到特定范围内的素数哈希表大小时。如果N
约为2 ^ 30,那么您真的要进行30000
除法测试以查找任何因素吗?显然不是。

解决此问题的常用方法是一个简单的测试,称为
Euler可能素数测试,一个更强大的泛化,称为强概率素数(SPRP)。 。这是一个对于整数
可以将N概率地归类为素数的测试,而
重复测试可以提高正确性的概率。测试本身的最慢部分主要涉及计算与A ^(N-1)模N类似的值。实现RSA公钥加密
变体的任何人都使用了此算法。对于巨大的整数
(例如512位)以及普通的32或64位整数,这都是有用的。

可以将测试从概率拒绝更改为确定的证明。通过预先计算某些在N范围内总是成功的测试输入来确定素数。
不幸的是,发现这些“最知名的测试”实际上是对一个巨大的(在事实无限)域。 1980年,卡尔·波默兰斯(Carl Pomerance)创建了第一个有用的测试列表(以测试为名
后来,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

#4 楼

有一个100%的数学测试,称为qS120120qq是质数还是复合数,称为AKS Primality Test。

概念很简单:给定数字P,如果P的所有系数都可以被(x-1)^P - (x^P-1)整除,则P是质数,否则是一个复合数。

例如,给定P,将得出多项式:

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


系数均可以被P = 3整除,因此数字为质数。

还有一个不是素数的3将产生的示例:

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


在这里我们可以看到系数P = 4不可除由6组成,因此它不是素数。

多项式4将具有(x-1)^P项,可以使用组合找到。因此,此测试将在P+1运行时中运行,所以我不知道这会有多大用处,因为您可以简单地将O(n)从0迭代到i,然后测试其余部分。

评论


AKS在实践中是一种非常缓慢的方法,与其他已知方法不具有竞争力。您所描述的方法不是AKS,而是比未优化的试验划分(如您所指出的)要慢的开放引理。

– DanaJ
2014-11-29 6:41



你好@ Kousha,x代表什么?在(x-1)^ P-(x ^ P-1)中。您是否有示例代码?在C ++中确定整数是否为质数?

–kiLLua
16-10-5在7:59



@kiLLua X只是一个变量。 X的系数确定数字是否为质数。不,我没有代码。我不建议实际使用此方法来确定数字是否为质数。这只是素数的一个很酷的数学行为,但否则效率极低。

–库萨
16-10-6在18:24

#5 楼

您是否要确定某个数字是否为质数?然后,您需要进行素数测试(简单)。还是您需要所有给定数的素数?在那种情况下,主要的筛子是好的(容易,但需要记忆)。还是您需要数字的主要因素?这将需要分解(如果您确实想要最有效的方法,则很难进行大量运算)。您要查看的数字有多大? 16位? 32位?更大吗?

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

评论


一个好的素数测试与可以合理适合的素数表的主内存延迟相比具有竞争力,因此,除非它适合L2,否则我不会使用它。

–查尔斯
2011年8月19日下午4:37

#6 楼

这取决于您的应用程序。有一些注意事项:


您是否只需要一些数字是否为质数的信息,是否需要达到一定限制的所有质数,或者是否(可能)全部质数?
您必须处理多少个数?

对于一定大小以上的数字(某些地方大约有几个,Miller-Rabin和模拟测试仅比筛子快)我相信)。在此之下,使用试验师(如果您只有几个数字)或筛子更快。

#7 楼

Rabin-Miller是标准的概率素数测试。 (您将其运行了K次,并且输入数字肯定是复合的,或者它可能是素数,出现错误的可能性为4-K。(几百次迭代,几乎可以肯定地说出了事实)

Rabin Miller有一个非概率(确定性)变体。

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

#8 楼

我会让您决定它是否最快。

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


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

评论


这太慢了。问题是我<=(ToCheck / 3)。它应该是我<=(ToCheck / i)。使用它,它可能会在0.1秒内运行。

–尼斯
18-10-10在15:11



#9 楼

我今天用C编写,与tcc一起编写,是几年前在准备竞争性考试时发现的。不知道有没有人写过它。它确实非常快(但是您应该决定是否很快)。花一两分钟在i7处理器上找出大约1,00,004个质数在10到1,00,00,000之间,平均CPU使用率为32%。
您知道,只有那些最后一位数字为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;
}


#10 楼

#include <stdio.h>

int main() //works for first 10000 primes.
{
#define LEAST_PRIME 2

int remainder, number_to_be_checked = LEAST_PRIME, divisor = 2, remainder_dump, 
upper_limit; //upper limit to be specified by user.
int i = 1;
printf("            SPECIFY UPPER LIMIT:   ");
scanf("%d", &upper_limit);
printf("1. 2,\n", number_to_be_checked); //PRINTS 2.
do
{
    remainder_dump = 1;
    divisor = 2;

    do
    {
        remainder = number_to_be_checked % divisor;
        if (remainder == 0)
        {
            remainder_dump = remainder_dump * remainder; // dumping 0 for rejection.
        }
        ++divisor;

    } while (divisor <= number_to_be_checked/divisor); // upto here we know number is prime or 
not.
    if (remainder_dump != 0)
    {
        ++i;
        printf("%d.) %d.\t", i, number_to_be_checked); //print if prime.
    };
    number_to_be_checked = number_to_be_checked + 1;
} while (number_to_be_checked <= upper_limit);
printf("\nNUMBER OF PRIMES:           \t%d", i);

return 0;
}

可以无限期列出质数。很抱歉,我只花了3天的时间就编写了该程序,因此它使用了非常基本的功能。
在注释部分中建议的编辑后,它在13秒钟内最多输出100万个素数。

评论


DAMNNNNNN!它是DAMNNN的快速。 THNKSSSSSS ..............

– Samarthya Singh
12月19日4:36

但是,当我将上限指定为104729时,似乎应该出现问题,它应将质数数设为10065,而不是正确的答案10000。我们是否也应采用number_to_be_checked的rt?

– Samarthya Singh
12月19日4:43

有效!!!但是如何?至于在同一台计算机上,wayyy的速度要快13秒钟,因此与之相比,要花13秒钟。

– Samarthya Singh
12月19日4:53



如果数字n不是质数,它将具有至少1个除数<= n的平方根。 n越大,速度差(迭代到n或平方根)就越明显。

–chux-恢复莫妮卡
12月19日4:55



可以通过“关注”按钮“关注”问题和答案。

–chux-恢复莫妮卡
12月19日5:00

#11 楼

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

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


#12 楼

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


评论


r在初始化之前使用

– zumalifeguard
2011-12-14 3:44

#13 楼

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


评论


这应该是“如何在不实际使用GOTO的情况下编写非结构化代码”的答案。所有这些混淆只是为了编写一个简单的试验师! (n%2)+1+(3 * n)还是不错的。 :)

–尼斯
2012年3月4日在21:25

@Will Ness我会否决这个问题的答案;为什么在宏会用时使用for循环? :)

–Rob Grant
2014年2月11日在10:54

#14 楼

我知道会晚一些,但这对于通过搜索到达此处的人们可能很有用。无论如何,这里有一些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
}


评论


如果生成大量素数,这会给您带来很多麻烦,并且为了进行比较,最好使用P [j] * P [j] <= k,因为sqrt非常慢

–西蒙
2014年6月26日17:51

@Simon sqrt可以从循环中吊起,并且只能计算一次,而P [j] * P [j]必须在每次迭代时计算。如果没有测试,我不会认为一个比另一个要快。

– Mark Ransom
12月19日4:18

#15 楼

#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<<", ";

    }
}


评论


这是最慢的事情。

–尼斯
2012年12月12日18:16

这很慢,如果上限是说10000000,那么此代码将消耗大量时间!

– Dixit Singla
13年11月16日在11:36

该代码为O(N ^ 2 / log N)。不间断O(N ^ 2)甚至会更慢,但这已经可以看作是编码错误。通过质数的保存和测试为O(N ^ 2 /(log N)^ 2),仅在数字的平方根以下的质数进行测试是O(N ^ 1.5 /(log N)^ 2)。

–尼斯
2014年8月11日在9:27

@WillNess也许有点夸张。他可以轻松地从1而不是2开始for循环,并添加j <= i而不是j
–肯尼·卡森(Kenny Cason)
16-10-4在0:30



我认为不应删除此帖子,它可以作为有价值的反例。

–尼斯
16-10-4在9:51