DIV CSS 佈局教程網

用 JavaScript 求 1 到 100 之間的所有素數
編輯:JavaScript基礎知識     

素數(質數)的定義是:大於 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 遍歷到 100,每一輪處理一個候選數 i。
  2. 內層循環讓 u 從 i 倒數到 1,凡是能整除 i 的就累加計數器 a。
  3. 循環結束後判斷 a 是否等於 2,等於 2 說明只有 1 和自身兩個因數,即為素數。

注意 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 以內的素數時,它的效率遠高於逐個試除。

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