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

哪个是使用C++查找素数的最快算法？我使用筛选算法,但我仍然希望它更快!

1> Greg Hewgill..：

---

阿特金的筛子的快速实施是丹伯恩斯坦的素原.这种筛子比Eratosthenes的筛子效率更高.他的页面有一些基准信息.

---

实际上我认为Primegen不是最快的,甚至是第二快的; 我认为yafu和primesieve一般都比较快,当然超过2 ^ 32.两者都是(改良的)Eratosthenes筛,而不是Atkin-Bernstein筛.

---

续:伯恩斯坦只使用与SoA相同的有效车轮分解来比较SoE,SoA是一个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%,具有相同的操作循环优化.

---

续2:由于2; 3; 5分解轮是算法的"烘入"部分,因此SoA con没有更高的因子轮分解用于产生很大的差异.

---

[Primesieve](https://code.google.com/p/primesieve/)Eveosthenes筛选(SoE)是最快的算法,并且总是比任何Atkin SoA筛选的实施都快,包括伯恩斯坦的链接在这个答案中,因为与SoA相比,primesieve减少了操作次数:对于32位数字范围(2 ^ 32 - 1),primesieve做了大约12亿次剔除,而SoA总共进行了大约14亿次组合切换和无方差操作这两种操作具有大致相同的复杂性,并且能够以大致相同的方式进行优化.

---

@Eamon Nerbonne,WP是正确的; 然而,仅仅具有稍微更好的计算复杂度并不能使通用的算法更快.在这些评论中,我指的是Eratosthenes筛选(SoE)的最大叶轮分解(这对于Atkin-SoA筛选是不可能的)使得SoE的操作略微减少到大约10亿的范围.在这一点之上,人们通常需要使用页面分段来克服内存限制,这就是SoA失败的地方,随着范围的增加,需要快速增加不断增加的开销.

2> Georg Schöll..：

---

如果它必须非常快,你可以包括一个素数列表:http:
//www.bigprimes.net/archive/prime/

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

---

肯定有1亿是与无穷大相比"少数";)

---

如果你拨打100000000,那么是的.:)

---

为什么你认为阿特金筛选(SoA)比Eratosthenes筛选(SoE)更快？当你使用伪代码实现一个程序时,肯定不是你链接的维基百科文章.如果使用与SoA一样的可能优化级别来实现SoE,那么SoA的非常大的筛分范围的操作比SoE略少,但是这种增益通常会被增加的复杂性和这种计算复杂性的额外恒定因子开销使得对于实际应用而言,SoE更好.

---

所有素数列表？我想你的意思是前几个素数列表...... :)

3> Mack..：

---

他,我知道我是一个问题死灵法师回答旧问题,但我刚刚在网上找到了这个问题,以寻求实现有效素数测试的方法.

到目前为止,我认为最快的素数测试算法是Strong Probable Prime(SPRP).我引用了Nvidia CUDA论坛:

数论中更实际的利基问题之一与质数的识别有关.给定N,你如何有效地确定它是否是素数？这不仅仅是一个问题,它可能是代码中需要的真正问题,也许当您需要动态查找特定范围内的主要哈希表大小时.如果N大约为2 ^ 30,你真的想做30000分区测试来搜索任何因素吗？显然不是.

这个问题的常见实际解决方案是一个称为Euler概率素数测试的简单测试,以及一个称为强可能素数(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正在奖金从$ 50K到$ 250K:https: //www.eff.org/awards/coop

4> Kousha..：

---

有一个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,因此数字是素数.

例如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并测试余数.

---

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

5> Christian Li..：

---

你的问题是决定一个特定的数字是否是素数？然后你需要一个素性测试(简单).或者你需要所有素数达到给定数量？在那种情况下,素筛是好的(容易,但需要记忆).或者你需要一个数字的素因子？这将需要分解(如果你真的想要最有效的方法,那么对于大数字很难).你看的数字有多大？16位？32位？大？

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