這篇要談一個篩素數的小技巧,能把需要檢查的候選數量大幅砍掉。
任何一個自然數,都可以寫成下列六種形式之一:
6N、6N+1、6N+2、6N+3、6N+4、6N+5 (N = 0, 1, 2, …)
顯然,當 N ≥ 1 時,6N、6N+2、6N+3、6N+4 都不可能是素數——前兩者能被 2 整除,後兩者分別能被 3 整除。也就是說,只有形如 6N+1 與 6N+5 的自然數才有機會是素數。因此,除了 2 和 3 這兩個例外,所有素數都能寫成 6N±1 的形式(N 為自然數)。
依據這個觀察,我們可以只對 6N±1 這類數字做篩選,候選數量直接降到原本的三分之一,篩選次數少了,執行效率自然就跟著提升。
以下範例要求傳入的自然數大於 10:
function fn(num){
var arr = [];
arr.push(2);
arr.push(3);
arr.push(5);
arr.push(7);
var t = 0;
for (var i = 3; t < num; i = i + 3) {
for (var j = 0; j < 2; j++) {
t = 2 * (i + j) - 1;
if (t < num && (t % 5 == 0 ? false : t % 7 == 0 ? false : true)) {
arr.push(t);
}
}
}
return arr.join(" ");
}
document.write(fn(1000));
先把 2、3、5、7 四個小素數直接寫進結果陣列,接著讓 i 以 3 為步長遞增,內層再用 j 取 0 與 1 兩輪,構造出的 t 依序為 6k−1 與 6k+1,正好對應 6N±1 的兩支。最後再用 5 與 7 做一次快速排除,進一步濾掉 5 與 7 的倍數。
值得留意的是,這份程式碼在「排除因數」這一步只檢查到 7 為止,所以當 num 大到某個程度時,結果裡會混進 11×11 這類的合數。若要更嚴謹,判斷條件應該換成「是否存在小於或等於 √t 的因數」,並把已知素數都存在一個陣列裡逐一試除——這也就是所謂的試除法,而本文的 6N±1 則是套在它外面的候選生成器。兩者結合,才是實務上常見的組合。
如果你有更高效率的做法,或是發現上面的程式碼有問題,歡迎提出來一起討論。