萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 實現質數判斷與篩選:從基礎算法到高性能優化

基礎判斷函數


/**
 * 判斷正整數是否為質數
 * @param {number} num - 待判斷整數(≥1)
 * @returns {boolean}
 */
function isPrime(num) {
  if (num <= 1) return false;   // 1 不是質數
  if (num === 2) return true;   // 2 是唯一偶質數
  if (num % 2 === 0) return false; // 排除其他偶數
  
  // 僅需檢查到 √num,步長 2 跳過偶數
  const limit = Math.sqrt(num);
  for (let i = 3; i <= limit; i += 2) {
    if (num % i === 0) return false;
  }
  return true;
}

範圍內質數篩選:埃拉托斯特尼篩法

單獨調用 isPrime 遍歷 1~N 效率較低(O(N√N))。篩法 可在 O(N log log N) 內一次性篩出所有質數。


/**
 * 埃拉托斯特尼篩法:獲取 ≤ limit 的所有質數
 * @param {number} limit - 上限(含)
 * @returns {number[]} 質數陣列
 */
function sieveOfEratosthenes(limit) {
  if (limit < 2) return [];
  
  // 標記數組:true 表示合數,false 表示質數候選
  const isComposite = new Array(limit + 1).fill(false);
  const primes = [];
  
  for (let i = 2; i <= limit; i++) {
    if (!isComposite[i]) {
      primes.push(i);
      // 標記 i 的倍數為合數(從 i*i 開始,步長 i)
      if (i * i <= limit) {
        for (let j = i * i; j <= limit; j += i) {
          isComposite[j] = true;
        }
      }
    }
  }
  return primes;
}

// 使用示例
const primes = sieveOfEratosthenes(100000); // 10萬內質數,瞬間完成
console.log(`共 ${primes.length} 個質數,最大: ${primes[primes.length-1]}`);

性能對比(Node.js 18 / Chrome V8 基準)

方法1萬10萬100萬1000萬
逐個 isPrime ~5ms ~60ms ~800ms ~12s
埃拉托斯特尼篩 ~1ms ~4ms ~40ms ~500ms
線性篩 (O(N)) ~1ms ~3ms ~30ms ~350ms

線性篩(歐拉篩)實現:O(N) 復雜度


/**
 * 線性篩:每個合數僅被最小質因子標記一次
 * @param {number} limit
 * @returns {number[]}
 */
function linearSieve(limit) {
  if (limit < 2) return [];
  const isComposite = new Array(limit + 1).fill(false);
  const primes = [];
  
  for (let i = 2; i <= limit; i++) {
    if (!isComposite[i]) primes.push(i);
    
    for (let j = 0; j < primes.length; j++) {
      const p = primes[j];
      const multiple = i * p;
      if (multiple > limit) break;
      isComposite[multiple] = true;
      if (i % p === 0) break; // 關鍵:保證每個合數只被最小質因子標記一次
    }
  }
  return primes;
}

大數質數判斷:Miller-Rabin 概率測試

對於 64 位整數(< 2^64),確定性 Miller-Rabin 只需測試固定基數集即可 100% 正確。


/**
 * 確定性 Miller-Rabin(適用 < 2^64)
 * @param {number|bigint} n
 * @returns {boolean}
 */
function isPrimeMR(n) {
  if (n < 2) return false;
  // 小質數快速過濾
  const smallPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
  for (const p of smallPrimes) {
    if (n === p) return true;
    if (n % p === 0) return false;
  }
  
  // 寫入 n-1 = d * 2^s
  let d = n - 1n;
  let s = 0;
  while ((d & 1n) === 0n) { d >>= 1n; s++; }
  
  // 確定性基數集(< 2^64)
  const bases = [2n, 325n, 9375n, 28178n, 450775n, 9780504n, 1795265022n];
  
  for (const a of bases) {
    if (a % n === 0n) continue;
    let x = modPow(a, d, n);
    if (x === 1n || x === n - 1n) continue;
    
    let composite = true;
    for (let r = 1; r < s; r++) {
      x = (x * x) % n;
      if (x === n - 1n) { composite = false; break; }
    }
    if (composite) return false;
  }
  return true;
}

// 模冪:(base^exp) % mod
function modPow(base, exp, mod) {
  let result = 1n;
  base %= mod;
  while (exp > 0) {
    if (exp & 1n) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return result;
}

實際應用場景

  1. 哈希表容量:選擇質數作為桶數組長度,減少哈希衝突。
  2. 加密算法:RSA 密鑰生成需大質數(用 Miller-Rabin)。
  3. 負載均衡:一致性哈希環節點數取質數。
  4. 隨機數生成:線性同餘法模數取質數。
  5. 算法題/競程:質數篩、質因子分解、互質判斷。

Web Worker 離線計算(避免阻塞主線程)


// prime-worker.js
self.onmessage = function(e) {
  const primes = linearSieve(e.data.limit);
  self.postMessage(primes);
};

// 主線程
const worker = new Worker('prime-worker.js');
worker.postMessage({ limit: 10000000 });
worker.onmessage = e => console.log('質數數量:', e.data.length);

總結

  • 單次判斷:isPrime(試除法至 √n,跳過偶數)。
  • 範圍批量:線性篩 (O(N)) 為首選,代碼簡短、速度極快、記憶體友好。
  • 大數(>1e12):Miller-Rabin 確定性版本(BigInt 實現)。
  • 前端大量計算:Web Worker 離線執行,不阻塞 UI。
  • 工程中預計算/緩存質數表(如 1e6 內質數僅 78498 個,JSON 僅 ~0.7MB),運行時直接查表最快。
copyright © 萬盛學電腦網 all rights reserved