哪个是找到素数最快的算法？
哪个是用C ++查找素数的最快算法？ 我已经使用sieve的算法，但我仍然希望它更快！
阿特金的筛子非常快速的实现是丹·伯恩斯坦的创始人 。 这个筛子比Eratosthenes的筛子更有效率。 他的页面有一些基准信息。
如果它必须非常快，你可以包括一个素数列表：
http://www.bigprimes.net/archive/prime/
如果您只需要知道某个数字是否是一个素数，那么在维基百科上列出了各种主要测试 。 他们可能是确定大数是否为素数的最快方法，尤其是因为他们可以告诉你数字是否不是素数。
他，我知道我是一个问题的死灵回答老问题，但我刚刚发现这个问题搜索网络的方式来实施有效的素数测试。
到目前为止，我认为最快的素数测试算法是强可能素数（SPRP）。 我从Nvidia CUDA论坛引用：
数论中更实际的小生境问题之一与素数的识别有关。 给定N，如何有效地确定它是否为素数？ 这不仅仅是一个棘手的问题，它可能是一个真正需要的代码，也许当你需要动态地在一定范围内找到一个主要散列表大小时。 如果N大约是2 ^ 30，那么你真的想做3万个分项测试来搜索任何因素吗？ 很明显不是。
这个问题的常见的实际解决方案是一个简单的测试，称为欧拉概率主要测试（Euler probable prime test），以及称为强可能性总理（Strong Probable Prime，SPRP）的更强大的泛化。 这是一个测试，对于一个整数N可以概率地将其归类为质数，重复测试可以增加正确性概率。 测试本身的缓慢部分主要涉及计算类似于A ^（N-1）模N的值。实施RSA公钥加密变体的任何人已经使用该算法。 对于大整数（如512位）以及普通的32位或64位整数都是有用的。
通过预先计算某些测试输入参数，可以将测试从概率拒绝改变为确定的有效性证明，这些测试输入参数已知在N的范围内总是成功。不幸的是，发现这些“最知名测试”实际上是搜索巨大其实是无限的）域名。 1980年，Carl Pomerance创建了第一个有用的测试列表（以其二次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测试来验证梅森素数。 梅森素数的形式是2 ^ p-1。 我认为Lucas-Lehmer测试是梅森素数最快的算法。
如果您不仅想要使用最快的算法，而且要使用最快的硬件，请尝试使用Nvidia CUDA来实现，为CUDA编写内核并在GPU上运行。
如果你发现足够多的素数，你甚至可以赚到一些钱，EFF会给予奖金从5万美元到25万美元： https ： //www.eff.org/awards/coop
有一个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和测试其余部分。
你的问题是要决定一个特定的数字是否是总数？ 那么你需要一个素性测试（简单）。 或者你需要所有素数达到给定数量？ 在这种情况下，主筛是好的（容易，但需要记忆）。 还是你需要一个数字的主要因素？ 这将需要分解（如果你真的想要最有效的方法很难大数目）。 你看的数字有多大？ 16位？ 32位？ 大？
一个聪明而有效的方法是预先计算素数表并使用位级编码将它们保存在文件中。 该文件被认为是一个长位矢量，而位n表示整数n。 如果n是素数，则其位被设置为1，否则为0。 查找速度非常快（您计算字节偏移量和位掩码），并且不需要将文件加载到内存中。
这取决于你的应用程序。 有一些考虑因素：
- 你是否只需要一些数字是否为素数的信息，你是否需要所有素数达到一定的限制，或者你是否需要（可能）所有素数？
- 你需要处理的数字有多大？
米勒 – 拉宾和模拟测试只比数量超过一定数量的筛子更快（我相信大概有几百万）。 在那之下，使用一个试验部门（如果你只有几个数字）或一个筛子是更快的。
拉宾 – 米勒是标准的概率素性测试。 （你运行了K次，输入的数字要么是复合的，要么是错误4 -K的概率（几百次迭代，这几乎肯定会告诉你真相）
拉宾·米勒有一个非概率的（确定的） 变体 。
已经发现了世界上最大的被证明的素数（截至2017年6月2 74,207,281 – 1）的互联网梅森素数搜索 （GIMPS）使用了几种算法 ，但是这些都是特殊形式的素数。 但是上面的GIMPS页面确实包含了一些通用的确定性素性测试。 它们似乎表明哪个算法是“最快的”取决于要测试的数量的大小。 如果你的数字适合64位，那么你可能不应该使用一种方法来处理数百万位数的素数。
我总是使用这个方法来计算质数，然后用筛选算法。
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); }
#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); }
#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; }
我知道这有点晚，但这对于从搜索到达这里的人来说可能是有用的。 无论如何，这里有一些JavaScript依赖于只有素数因子需要测试的事实，所以代码生成的更早的素数被重新用作后来的测试因子。 当然，所有偶数和模数值都会先被滤掉。 结果将在数组P中，并且这个代码可以在一台i7 PC（或者大约20个亿）中在1.5秒内收缩1000万个质数。 用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 }
#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<<", "; } }
