language-agnostic - 计算无限质数的方法

Question

好吧，所以也许我不应该把这个问题缩小太多......我已经看过关于找到前 10000 个素数的最有效方法的帖子。我正在寻找所有可能的方法。目标是为素性测试提供一站式服务。任何和所有人们知道的寻找素数的测试都是受欢迎的。

所以：

• 求素数有哪些不同的方法？

Answer 1

一些素数检验仅适用于某些数字，例如，Lucas-Lehmer检验仅适用于梅森数。

大多数用于大数的素数测试只能告诉您某个数字“可能是素数”（或者，如果该数字未通过测试，则它绝对不是素数）。通常你可以继续这个算法，直到你有一个非常高的概率是素数。

看看这个页面，尤其是它的“另见”部分。

我认为米勒-拉宾测试是最好的测试之一。在其标准形式中，它为您提供可能的素数 - 尽管已经表明，如果您将测试应用于 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. 如果列表中所有数字的余数都不为零，则整数是素数。

它使用的内存比埃拉托色尼筛法要少得多，而且对于单个数字通常更快。

Answer 4

@akdom 对我的问题：

根据我之前的建议，循环可以正常工作，您无需进行任何计算即可确定数字是否为偶数；在您的循环中，只需跳过每个偶数，如下所示：

//Assuming theInteger is the number to be tested for primality.
// Check if theInteger is divisible by 2.  If not, run this loop.
//  This loop skips all even numbers.
for( int i = 3; i < sqrt(theInteger); i + 2) 
{
    if( theInteger % i == 0) 
    {
       //getting here denotes that theInteger is not prime 
       // somehow indicate that some number, i, divides it and break
       break;
    }
}

Answer 5

罗格斯大学的一名研究生最近发现了一个产生素数的递归关系。其连续数字的差异将产生质数或 1。

a(1) = 7
a(n) = a(n-1) + gcd(n,a(n-1)). 

它产生了很多需要过滤掉的废话。Benoit Cloitre 也有这个重复执行类似任务：

b(1) = 1
b(n) = b(n-1) + lcm(n,b(n-1))

那么连续数之比减一 [b(n)/b(n-1)-1] 是素数。可以在Recursivity阅读所有这些的完整说明。

对于筛子，您可以使用轮子而不是每次都添加一个轮子来做得更好，请查看改进的增量素数筛子。这是一个轮子的例子。让我们看一下要忽略的数字 2 和 5。他们的轮子是 [2,4,2,2]。

Answer 6

在使用从 2 到整数根的列表的算法中，您可以通过仅测试 2 之后的奇数来提高性能。也就是说，您的列表只需要包含 2 和从 3 到整数平方根的所有奇数. 这将循环次数减少了一半，而不会增加任何复杂性。

Answer 7

@theprise

如果我想使用递增循环而不是实例化列表（大量数字的内存问题......），那么不构建列表的好方法是什么？

对给定整数 (X % 3) 进行整除性检查似乎并不比仅检查正常数 (N % X) 便宜。

Answer 8

如果您想找到一种生成素数的方法，这已在上一个问题中介绍过。