萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 輸出 1000 以內質數:從暴力法到埃拉托斯特尼篩法優化

題目需求

列出 1000 以內所有質數(素數):只能被 1 和自身整除的大於 1 的自然數。

方法一:暴力雙重循環(原始代碼)

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

複雜度:O(n²) ≈ 50 萬次模運算。1000 內尚可接受,但擴展到 10⁶ 會極慢。

方法二:試除法優化(√n 判斷)

<?php
function isPrime(int $n): bool {
    if ($n < 2) return false;
    if ($n === 2) return true;
    if ($n % 2 === 0) return false;
    for ($i = 3; $i * $i <= $n; $i += 2) { // 只檢查奇數,至多 √n
        if ($n % $i === 0) return false;
    }
    return true;
}

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

複雜度:O(n√n) ≈ 1.6 萬次模運算,快 30 倍。

方法三:埃拉托斯特尼篩法—— 經典 O(n log log n)

<?php
function sieve(int $limit): array {
    $isPrime = array_fill(0, $limit + 1, true);
    $isPrime[0] = $isPrime[1] = false;

    for ($i = 2; $i * $i <= $limit; $i++) {
        if ($isPrime[$i]) {
            // 從 i*i 開始標記,步長 i
            for ($j = $i * $i; $j <= $limit; $j += $i) {
                $isPrime[$j] = false;
            }
        }
    }
    return array_keys(array_filter($isPrime));
}

$primes = sieve(1000);
echo implode(' ', $primes); // 2 3 5 7 11 ... 997

優勢:無除法運算,純布林標記,極快。10⁶ 內質數只需 ~0.01s。

方法四:線性篩(歐拉篩)O(n) —— 進階

<?php
function linearSieve(int $limit): array {
    $isPrime = array_fill(0, $limit + 1, true);
    $primes = [];
    $isPrime[0] = $isPrime[1] = false;

    for ($i = 2; $i <= $limit; $i++) {
        if ($isPrime[$i]) $primes[] = $i;
        foreach ($primes as $p) {
            if ($i * $p > $limit) break;
            $isPrime[$i * $p] = false;
            if ($i % $p === 0) break; // 核心:保證每個合數只被最小質因子標記一次
        }
    }
    return $primes;
}

效能對比(PHP 8.2,1000 萬以內質數計數)

算法100010⁵10⁶10⁷記憶體
暴力雙循環0.002s2.1s——O(1)
試除法 √n0.001s0.15s1.8s—O(1)
埃氏篩<0.001s0.008s0.09s1.1sO(n) 布林陣列
線性篩<0.001s0.012s0.13s1.5sO(n) + 質數表

※ 10⁷ 以上 PHP 純陣列操作記憶體壓力大,建議改用 C 擴展或位圖優化。

位圖優化版埃氏篩(節省 8 倍記憶體)

<?php
function sieveBitset(int $limit): array {
    $size = (int)(($limit + 7) / 8);
    $bits = str_repeat("\xFF", $size); // 全 1 = 可能是質數
    $bits[0] = chr(ord($bits[0]) & ~0x03); // 0,1 非質數

    for ($i = 2; $i * $i <= $limit; $i++) {
        $byte = $i >> 3;
        $bit  = $i & 7;
        if (ord($bits[$byte]) & (1 << $bit)) { // 是質數
            for ($j = $i * $i; $j <= $limit; $j += $i) {
                $bits[$j >> 3] = chr(ord($bits[$j >> 3]) & ~(1 << ($j & 7)));
            }
        }
    }
    $primes = [];
    for ($i = 2; $i <= $limit; $i++) {
        if (ord($bits[$i >> 3]) & (1 << ($i & 7))) $primes[] = $i;
    }
    return $primes;
}

實用工具函數:質數判斷與分解

<?php
// 判斷大數是否質數(米勒-拉賓確定性版本,適用 64 位整數)
function isPrimeMR(int $n): bool {
    if ($n < 2) return false;
    foreach ([2,3,5,7,11,13,17,19,23,29,31,37] as $p) {
        if ($n % $p === 0) return $n === $p;
    }
    $d = $n - 1; $s = 0;
    while ($d % 2 === 0) { $d >>= 1; $s++; }
    foreach ([2, 325, 9375, 28178, 450775, 9780504, 1795265022] as $a) {
        if ($a % $n === 0) continue;
        $x = powmod($a, $d, $n);
        if ($x === 1 || $x === $n-1) continue;
        for ($r = 1; $r < $s; $r++) {
            $x = ($x * $x) % $n;
            if ($x === $n-1) break;
        }
        if ($x !== $n-1) return false;
    }
    return true;
}
function powmod(int $a, int $e, int $m): int {
    $r = 1; $a %= $m;
    while ($e) { if ($e & 1) $r = ($r * $a) % $m; $a = ($a * $a) % $m; $e >>= 1; }
    return $r;
}

結語:教學/面試常考暴力法與埃氏篩;工程上 10⁶ 以內直接用埃氏篩;大數質數判斷用 Miller-Rabin;極大範圍(10⁹+)需分段篩或 C++/Rust 實現。

copyright © 萬盛學電腦網 all rights reserved