素數(質數)的定義是:大於 1 且只能被 1 和自身整除的自然數。判斷一個數是不是素數,最直觀的思路就是統計它能被多少個數整除——如果恰好是 2 個(1 和它本身),那就是素數。
for (var i = 1; i <= 100; ++i) {
var a = 0; // 計數器,統計因數個數
for (var u = i; u >= 1; --u) {
if (i % u === 0) {
++a;
}
}
if (a === 2) {
console.log(i);
}
}
注意 1 不是素數——它的因數只有 1 個,因此在 a === 2 的判斷下會被自動排除。
上面的做法對每個數都從 1 試到自身,存在大量無效計算。有幾個常見的改進方向:
// 優化一:只需試到平方根,且遇到第一個因數就提前退出
function isPrime(n) {
if (n < 2) return false;
for (var i = 2; i * i <= n; i++) {
if (n % i === 0) return false;
}
return true;
}
var result = [];
for (var j = 1; j <= 100; j++) {
if (isPrime(j)) result.push(j);
}
console.log(result);
為什麼試到平方根就夠了?因為如果 n 存在大於其平方根的因數,那麼必然同時存在一個小於平方根的配對因數,早在前面就被判斷掉了。這個改進把內層循環從 n 次降到約 √n 次。
// 優化二:埃拉托斯特尼篩法(Sieve of Eratosthenes)
function sieve(max) {
var isPrime = new Array(max + 1).fill(true);
isPrime[0] = isPrime[1] = false;
for (var i = 2; i * i <= max; i++) {
if (isPrime[i]) {
for (var j = i * i; j <= max; j += i) {
isPrime[j] = false; // 把 i 的所有倍數標記為合數
}
}
}
return isPrime;
}
var table = sieve(100);
var primes = [];
for (var k = 2; k <= 100; k++) {
if (table[k]) primes.push(k);
}
console.log(primes);
篩法的思路與前面完全不同:不去一個個判斷,而是反過來把每個素數的倍數統統劃掉,剩下的就是素數。求 100 以內的素數時,它的效率遠高於逐個試除。