php求素数的方法 - 埃拉托色尼的筛选法(Sieve of Eratosthenes)

1. 概述

素数是指只能被1和自身整除的数，求解素数一直是编程中的常见问题之一。本文将介绍一种高效的求素数方法——埃拉托色尼的筛选法（Sieve of Eratosthenes）。该方法通过先标记质数，然后将质数的倍数标记为非质数的方式，高效地找出一定范围内的所有素数。

2. 埃拉托色尼的筛选法

埃拉托色尼的筛选法是一种古老而经典的找素数算法。它的基本思想是：

创建一个长度为n+1的布尔数组，初始值都为true。

从2开始，将每个质数的倍数标记为false。

最后剩下的为true的数即为素数。

2.1 实现方法

下面是用PHP实现埃拉托色尼的筛选法的示例代码：

function sieveOfEratosthenes($n) {
    // 创建一个长度为n+1的布尔数组
    $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的布尔数组$isPrime，并将初始值都设置为true。然后，从2开始，如果某个数为质数，则将其倍数标记为false。最后，将值为true的数字作为素数存入$primes数组中。

2.2 示例说明

使用上述代码求解范围为100的素数，输出结果如下：

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

可以看到，范围为100的素数都能正确被找出。

3. 性能分析

埃拉托色尼的筛选法的时间复杂度为O(nloglogn)，在找出一定范围内的素数时具有很高的效率。该方法适用于求解较小范围内的素数。

4. 总结

本文介绍了一种高效的求素数方法——埃拉托色尼的筛选法。该方法通过先标记质数，然后将质数的倍数标记为非质数的方式，高效地找出一定范围内的所有素数。应用该方法，可以方便地解决素数相关的编程问题。