DIV CSS 佈局教程網

JS 實例教程:用 6N±1 法有效率地篩選素數
編輯:關於JavaScript     

這篇要談一個篩素數的小技巧,能把需要檢查的候選數量大幅砍掉。

原理:為什麼是 6N±1

任何一個自然數,都可以寫成下列六種形式之一:

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 則是套在它外面的候選生成器。兩者結合,才是實務上常見的組合。

如果你有更高效率的做法,或是發現上面的程式碼有問題,歡迎提出來一起討論。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved