质数算法效率

Question

我有一个关于素数算法的问题。

为什么在下面的伪代码中，我每次迭代增加6而不是2增加？

function is_prime(n) 
if n ≤ 1 
    return false 
else if n ≤ 3 
    return true 
else if n mod 2 = 0 or n mod 3 = 0 
    return false 
let i ← 5 
while i * i ≤ n 
    if n mod i = 0 or n mod (i + 2) = 0 
     return false 
    i ← i + 6 
return true 

谢谢！

Answer 1

如果它增加2它将测试几乎所有的两次，这是没有任何意义的。所以我假设你的意思是：如何不测试每一个奇数？

这是因为每个大于3的素数p的形式为6n±1。证明： 考虑余数r = p mod 6.显然r必须是奇数。还要注意，r不能是3，因为那么p可以被3整除，使得它不是素数。这只剩下可能性1和5，它们分别对应于形式6n + 1或形式6n-1的p。

其效果是它避免测试3的倍数。除以3的倍数是多余的，因为我们已经知道n不是3的倍数，因此它不能是3的倍数的倍数。

Answer 2

循环体中的赋值是i <- i + 6而不是i <- i + 2。在if声明中，表达式i + 2只是成为一个新值。该表达式中没有赋值运算符。

Answer 3

该算法基于素数可以使用公式6k ± 1进行预测，并且这不适用于2 and 3。

例如

(6 * 1) - 1 = 5

(6 * 2) - 1 = 11

(6 * 3) - 1 = 17

这样的例子不胜枚举和。