質數算法效率

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

這樣的例子不勝枚舉和。