计算无限素数的方法

Question

好吧，也许我不应该把这个问题缩小太多.我在找到前10000个素数最有效的方法上看过这篇文章。我正在寻找所有可能的方式，。我们的目标是为原始性测试提供一站式服务。所有人们知道的寻找素数的测试都是受欢迎的。

因此：

• ，寻找素数的不同方法是什么？

Answer 1

一些素数测试只适用于某些数字，例如，卢卡斯-莱默测试只适用于Mersenne数。

大多数用于大数的素数测试只能告诉您某个数字是“可能是素数”(或者，如果测试失败，它肯定是而不是素数)。通常，你可以继续这个算法，直到你有一个很高的概率，一个数字是素数。

看看此页，特别是它的“也请看”一节。

我认为，米勒-拉宾试验是最好的测试之一。在标准形式中，它给出了可能的素数--尽管已经表明，如果将测试应用于3.4*10^14以下的一个数字，并且它通过了每个参数2、3、5、7、11、13和17的测试，那么它肯定是素数。

AKS试验是第一个确定性的，证明的，一般的，多项式时间测试.然而，据我所知，它的最佳实现速度比其他测试慢，除非输入非常大。

Answer 2

伊拉托斯提尼的筛子是一个不错的算法：

1. 取正整数2的列表到任何给定的上限。
2. 获取列表中的下一项(第一次迭代中的2项)，并从列表中删除它的所有倍数(超过第一项)。
3. 重复第二步，直到达到给定的上限。
4. 你的名单现在完全由素数组成。

这种算法有一个功能限制，因为它用速度来交换内存。当生成非常大的素数列表时，内存容量就会急剧上升。

Answer 3

对于给定的整数，我所知道的最快的素数检查是：

1. 将2的列表取到的平方根，即整数。
2. 循环遍历列表，将的剩余部分取为整数/当前数字
   1. 如果列表中任何数字的余数为零，则整数不是素数。
   2. 如果对于列表中的所有数字，余数为非零，则整数为素数。

与伊拉托斯提尼的筛子相比，它使用的内存要少得多，而且对于单个数字来说通常更快。