判斷一個數字是否為質數,看似簡單,但仔細研究會發現學問不少。本文記錄從暴力解法到效能優化的完整歷程。
<script>
$(function () {
$("#submit").on('click', function () {
var num = $("#num").val();
if (isPrimeNum(num)) {
alert(num + "是質數");
} else {
alert(num + "是合數");
}
});
});
</script>
用 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 的數字必定不是質數,可提前排除。
把各位數字相加,若和能被 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)。過多的技巧判斷反而可能弄巧成拙,這也是一次很好的效能優化練習。