PHP生成素数列表的核心是高效准确的素数判定：基础法逐个试除至√n，适合小范围；筛法批量标记合数，适合大范围，时间复杂度O(n log log n)。
用PHP生成素数列表，核心是判断每个数是否为素数，再按需筛选输出。关键在于素数判定逻辑要高效、准确，避免低效的全范围试除。
什么是素数？
素数（质数）是指大于1的自然数，且仅能被1和它本身整除。注意：1不是素数，2是最小的素数，也是唯一的偶素数。
基础方法：逐一判断（适合小范围）
对每个待检数字 $n$，从2试除到 $\sqrt{n}$（含），若无整除则为素数。这是最直观、易理解的方式。
示例代码（生成1~100内的素数）：
立即学习“PHP免费学习笔记（深入）”；
function isPrime($n) {
if ($n < 2) return false;
if ($n == 2) return true;
if ($n % 2 == 0) return false;
for ($i = 3; $i * $i <= $n; $i += 2) {
if ($n % $i == 0) return false;
}
return true;
}
<p>$primes = [];
for ($num = 2; $num <= 100; $num++) {
if (isPrime($num)) {
$primes[] = $num;
}
}
print_r($primes);</p>优化方法：埃拉托斯特尼筛法（适合大范围）
当需要生成指定上限以内的全部素数时，筛法效率远高于逐个判断，时间复杂度约为 O(n log log n)。
- 创建一个布尔数组，初始假设所有数（2~n）都是素数
- 从2开始，将它的所有倍数（4,6,8…）标记为非素数
- 找到下一个未被标记的数（即下一个素数），重复上述步骤
- 遍历完成后，所有未被标记的数即为素数
示例代码（生成≤100的所有素数）：
function sieveOfEratosthenes($limit) {
if ($limit < 2) return [];
$isPrime = array_fill(0, $limit + 1, true);
$isPrime[0] = $isPrime[1] = false;
<pre class='brush:php;toolbar:false;'>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));
实用建议与注意事项
- 小范围（如≤1000）用基础判断法足够清晰、易调试
- 大范围（如≤10⁵）务必用筛法，否则性能急剧下降
- 注意整型溢出风险：$i * $i 可能超出 int 范围（尤其在32位环境），可用 $i <= (int)sqrt($n) 替代，但 sqrt 有浮点误差，推荐保持 $i * $i <= $n 并确保 $n 不过大
- 内存考虑：筛法需 O(n) 空间，超大上限（如1亿）可能内存不足，此时可考虑分段筛或轮式优化
不复杂但容易忽略细节，写对比写快更重要——先保证逻辑正确，再根据数据规模选策略。
