/**
* 判斷正整數是否為質數
* @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]}`);
| 方法 | 1萬 | 10萬 | 100萬 | 1000萬 |
|---|---|---|---|---|
| 逐個 isPrime | ~5ms | ~60ms | ~800ms | ~12s |
| 埃拉托斯特尼篩 | ~1ms | ~4ms | ~40ms | ~500ms |
| 線性篩 (O(N)) | ~1ms | ~3ms | ~30ms | ~350ms |
/**
* 線性篩:每個合數僅被最小質因子標記一次
* @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;
}
對於 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;
}
// 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,跳過偶數)。