素数算法效率
prime numbers algorithm efficiency
我有一个关于素数算法的问题。
为什么在下面的伪代码中 i 每次迭代都增加 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
谢谢！
循环体内的赋值是i <- i + 6，不是i <- i + 2。在 if 语句中，表达式 i + 2 只是变成了一个新值。该表达式中没有赋值运算符。
如果它增加 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的倍数，所以不可能是a的倍数3 的倍数。
该算法基于可以使用公式 6k ± 1 预测素数这一事实，这不适用于 2 and 3。
例如
(6 * 1) - 1 = 5
(6 * 2) - 1 = 11
(6 * 3) - 1 = 17
这样的例子不胜枚举。
我有一个关于素数算法的问题。
为什么在下面的伪代码中 i 每次迭代都增加 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
谢谢！
循环体内的赋值是i <- i + 6，不是i <- i + 2。在 if 语句中，表达式 i + 2 只是变成了一个新值。该表达式中没有赋值运算符。
如果它增加 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的倍数，所以不可能是a的倍数3 的倍数。
该算法基于可以使用公式 6k ± 1 预测素数这一事实，这不适用于 2 and 3。
例如
(6 * 1) - 1 = 5
(6 * 2) - 1 = 11
(6 * 3) - 1 = 17
这样的例子不胜枚举。