PHP 輸出 1000 以內質數的演算法優化

列出 1000 以內質數是經典入門練習。原始雙重迴圈雖正確但效能低落 (O(n²))。本文從基礎版逐步優化至 埃拉托斯特尼篩法，並提供基準測試對比。

版本 1：暴力法 (原始碼)

for ($i = 2; $i < 1001; $i++) {
    $primes = 0;
    for ($k = 1; $k <= $i; $k++)
        if ($i % $k === 0) $primes++;
    if ($primes <= 2)
        echo "$i
";
}

❌ 問題：$k=1 到 $i 全測，$i=1000 時執行 50萬次模運算。

版本 2：優化試除法 (O(n√n))

function isPrime($n) {
    if ($n < 2) return false;
    if ($n % 2 === 0) return $n === 2;
    for ($i = 3; $i * $i <= $n; $i += 2)
        if ($n % $i === 0) return false;
    return true;
}

for ($i = 2; $i < 1001; $i++)
    if (isPrime($i)) echo "$i
";

✅ 只測到 √n、跳過偶數，約快 50 倍。

版本 3：埃拉托斯特尼篩法 (O(n log log n)) - 推薦

function sievePrimes($limit) {
    $isPrime = array_fill(0, $limit + 1, true);
    $isPrime[0] = $isPrime[1] = false;
    
    for ($i = 2; $i * $i <= $limit; $i++) {
        if ($isPrime[$i]) {
            for ($j = $i * $i; $j <= $limit; $j += $i)
                $isPrime[$j] = false;
        }
    }
    return array_keys(array_filter($isPrime));
}

$primes = sievePrimes(1000);
echo implode(', ', $primes);
// 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97...

版本 4：位元優化篩法 (記憶體省 8 倍)

function sieveBits($limit) {
    $size = (int)(($limit - 1) / 2); // 僅存奇數
    $bits = array_fill(0, $size, true); // true = 可能為質數
    
    for ($i = 0; $i * $i < $size; $i++) {
        if ($bits[$i]) {
            $p = 2 * $i + 3; // 實際質數值
            for ($j = ($p * $p - 3) / 2; $j < $size; $j += $p)
                $bits[$j] = false;
        }
    }
    $primes = [2];
    foreach ($bits as $i => $v)
        if ($v) $primes[] = 2 * $i + 3;
    return $primes;
}

效能基準 (PHP 8.2, 100萬以內質數)

實務應用建議

• N < 10⁶：標準篩法足夠，程式碼簡潔易維護。
• N > 10⁷：位元篩法或分段篩法，避免記憶體爆炸。
• 單次判斷大數質數：Miller-Rabin 概率測試 (PHP 可用 gmp_prob_prime)。
• 常用質數表：預先計算存檔 (JSON/資料庫)，直接查表最快。

延伸：質因數分解

function primeFactors($n) {
    $factors = [];
    for ($p = 2; $p * $p <= $n; $p++) {
        while ($n % $p === 0) {
            $factors[] = $p;
            $n /= $p;
        }
    }
    if ($n > 1) $factors[] = $n;
    return $factors;
}
print_r(primeFactors(1000)); // [2,2,2,5,5,5]

篩法是質數生成的黃金標準，掌握其原理與變體，能輕鬆解決從競程到密碼學的各類質數問題。