列出 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⁶ 會極慢。
<?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 倍。
<?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。
<?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;
}
| 算法 | 1000 | 10⁵ | 10⁶ | 10⁷ | 記憶體 |
|---|---|---|---|---|---|
| 暴力雙循環 | 0.002s | 2.1s | — | — | O(1) |
| 試除法 √n | 0.001s | 0.15s | 1.8s | — | O(1) |
| 埃氏篩 | <0.001s | 0.008s | 0.09s | 1.1s | O(n) 布林陣列 |
| 線性篩 | <0.001s | 0.012s | 0.13s | 1.5s | O(n) + 質數表 |
※ 10⁷ 以上 PHP 純陣列操作記憶體壓力大,建議改用 C 擴展或位圖優化。
<?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 實現。