PHP實現高效素數篩選算法——埃拉托色尼篩法詳解

概述

素數指的是只能被1和自身整除的自然數，求素數是編程中常見的問題之一。本文介紹一種經典且高效的素數求解方法——埃拉托色尼篩選法（Sieve of Eratosthenes）。該算法通過標記質數及其倍數的方式，快速找出指定範圍內所有素數。

埃拉托色尼篩選法原理

埃拉托色尼篩選法是一種歷史悠久且簡單有效的算法，核心思路包括：

創建一個長度為n+1 的布爾數組，初始值均為true；

從2開始，將每個質數的倍數標記為false；

最終剩餘值為true 的元素即為素數。

PHP實現示例

以下示例代碼展示瞭如何使用PHP實現該篩選法：

 function sieveOfEratosthenes($n) {
    // 創建一個長度為 n+1 的布爾數組，初始值為 true
    $isPrime = array_fill(2, $n - 1, true);
    
    // 從2開始，將每個質數的倍數標記為 false
    for ($i = 2; $i * $i <= $n; $i++) {
        if ($isPrime[$i]) {
            for ($j = $i * $i; $j <= $n; $j += $i) {
                $isPrime[$j] = false;
            }
        }
    }
    
    // 收集所有為 true 的數，即素數
    $primes = [];
    foreach ($isPrime as $number => $is) {
        if ($is) {
            $primes[] = $number;
        }
    }
    return $primes;
}

$range = 100;
$primes = sieveOfEratosthenes($range);

// 輸出素數
foreach ($primes as $prime) {
    echo $prime . " ";
}

代碼首先創建了一個大小為n+1 的布爾數組，初始全部設為true，然後通過雙層循環將質數的倍數逐一標記為false。最後，將所有標記為true 的索引收集，即為素數集合。

示例運行結果

運行上述代碼，範圍為100的素數輸出如下：

 <span class="fun">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</span>

由此可見，該方法能夠準確且高效地找出給定範圍內的所有素數。

性能分析

埃拉托色尼篩選法的時間複雜度約為O(n log log n)，適合在較小至中等範圍內快速篩選素數。相比暴力判斷，每次篩選時排除更多非質數，極大提升性能。

總結

本文介紹了PHP實現的埃拉托色尼篩選法，這是一種簡單且高效的素數篩選算法。掌握此算法有助於解決涉及素數的編程問題，提高代碼效率和性能。