PHP百题：PHP编写程序生成素数列表-php教程-PHP中文网

php生成素数列表的核心是高效准确的素数判定：基础法逐个试除至√n，适合小范围；筛法批量标记合数，适合大范围，时间复杂度o(n log log n)。

php百题：php编写程序生成素数列表

用PHP生成素数列表，核心是判断每个数是否为素数，再按需筛选输出。关键在于素数判定逻辑要高效、准确，避免低效的全范围试除。

什么是素数？

素数（质数）是指大于1的自然数，且仅能被1和它本身整除。注意：1不是素数，2是最小的素数，也是唯一的偶素数。

基础方法：逐一判断（适合小范围）

对每个待检数字 $n$，从2试除到 $\sqrt{n}$（含），若无整除则为素数。这是最直观、易理解的方式。

示例代码（生成1~100内的素数）：

function isPrime($n) {
    if ($n $primes = [];
for ($num = 2; $num

优化方法：埃拉托斯特尼筛法（适合大范围）

当需要生成指定上限以内的全部素数时，筛法效率远高于逐个判断，时间复杂度约为 O(n log log n)。

btpanel phpsite 宝塔面板PHP网站

宝塔面板 PHP 网站管理：站点创建、删除、启停、PHP 版本切换、域名管理、SSL证书管理、伪静态管理、数据库管理

下载

创建一个布尔数组，初始假设所有数（2~n）都是素数
从2开始，将它的所有倍数（4,6,8…）标记为非素数
找到下一个未被标记的数（即下一个素数），重复上述步骤
遍历完成后，所有未被标记的数即为素数

示例代码（生成≤100的所有素数）：

function sieveOfEratosthenes($limit) {
    if ($limit for ($i = 2; $i * $i <= $limit; $i++) {
    if ($isPrime[$i]) {
        for ($j = $i * $i; $j <= $limit; $j += $i) {
            $isPrime[$j] = false;
        }
    }
}

$primes = [];
for ($i = 2; $i <= $limit; $i++) {
    if ($isPrime[$i]) $primes[] = $i;
}
return $primes;

}

print_r(sieveOfEratosthenes(100));