DIV CSS 佈局教程網

JavaScript 判斷質數的方法與效能優化實錄
編輯:關於JavaScript     

判斷一個數字是否為質數,看似簡單,但仔細研究會發現學問不少。本文記錄從暴力解法到效能優化的完整歷程。

基礎 DOM 與呼叫

<script>
$(function () {
  $("#submit").on('click', function () {
    var num = $("#num").val();
    if (isPrimeNum(num)) {
      alert(num + "是質數");
    } else {
      alert(num + "是合數");
    }
  });
});
</script>

方法一:基本 for 迴圈

用 2 以上的數字不斷與目標求餘數,若餘為 0 就是合數:

function isPrimeNum(num) {
  for (var i = 2; i < num; i++) {
    if (num % i == 0) { return false; }
  }
  return true;
}

優化一:只循環到一半

其實不必一直除到該數字本身,只需循環到 num/2 即可:

for (var i = 2; i < num / 2 + 1; i++) { ... }

優化二:排除尾數為偶數或 5 的數字

尾數為偶數或 5 的數字必定不是質數,可提前排除。

優化三:排除能被 3 整除的數字

把各位數字相加,若和能被 3 整除,該數也能被 3 整除。

最終寫法:只循環到平方根

經過實測,前面那些「自作聰明」的判斷本身也有運算成本,反而成了負優化。最科學的方式是只循環到 Math.sqrt(num):

function isPrimeNum(num) {
  if (!isNum(num)) { return false; }
  if (!isInteger(num)) { return false; }
  for (var i = 2; i <= Math.sqrt(num); i++) {
    if (num % i == 0) { return false; }
  }
  return true;
}
function isInteger(num) { return num == ~~num ? true : false; }
function isNum(num) { return num == +num ? true : false; }

實測顯示,只循環到平方根的版本,計算 100 萬以內所有質數約需一千多毫秒,比各種小技巧都更快。

附錄:一個正則表達式的神奇解法

function isPrimeNum2(num) {
  return !/^.?$|^(..+?)\1+$/.test(Array(num + 1).join('1'));
}

這段使用正則表達式的寫法雖然精簡到令人驚豔,但效能反而遠不如前述方法。

小結:判斷質數最實用且高效的方式,就是只循環到 Math.sqrt(num)。過多的技巧判斷反而可能弄巧成拙,這也是一次很好的效能優化練習。

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