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实现的埃拉托色尼筛选法，这是一种简单且高效的素数筛选算法。掌握此算法有助于解决涉及素数的编程问题，提高代码效率和性能。