PHP怎么判断素数并打印1~100的素数

发布时间：2021-08-23 13:35:37 作者：chen
来源：亿速云阅读：597

# PHP怎么判断素数并打印1~100的素数

## 什么是素数

素数（Prime Number）指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。换句话说，素数只能被1和它自身整除。例如：2、3、5、7、11等都是素数，而4、6、8、9等则不是（因为它们可以被其他数整除）。

## 判断素数的算法原理

要判断一个数n是否为素数，通常采用以下方法：

1. **基础判断**：如果n <= 1，直接返回false（素数定义要求大于1）
2. **特殊处理**：2是唯一的偶素数，可以直接返回true
3. **排除偶数**：如果n是大于2的偶数，直接返回false
4. **试除法**：检查从3到√n的所有奇数是否能整除n（因为如果n有因数，必定有一个小于等于√n）

## PHP实现素数判断函数

以下是PHP实现的素数判断函数：

```php
function isPrime($num) {
    if ($num <= 1) {
        return false;
    }
    if ($num == 2) {
        return true;
    }
    if ($num % 2 == 0) {
        return false;
    }
    for ($i = 3; $i <= sqrt($num); $i += 2) {
        if ($num % $i == 0) {
            return false;
        }
    }
    return true;
}

函数解析

$num <= 1：过滤掉非正整数和1
$num == 2：2是特殊素数，直接返回
$num % 2 == 0：排除所有大于2的偶数
for循环：从3开始，每次加2（跳过偶数），检查到√n为止

打印1~100的素数

现在我们需要遍历1到100的数字，使用上述函数判断并打印素数：

echo "1~100的素数有：\n";
for ($i = 1; $i <= 100; $i++) {
    if (isPrime($i)) {
        echo $i . " ";
    }
}

优化输出格式

为了使输出更美观，我们可以每行打印5个素数：

echo "1~100的素数有：\n";
$count = 0;
for ($i = 1; $i <= 100; $i++) {
    if (isPrime($i)) {
        echo str_pad($i, 3, " ", STR_PAD_LEFT);
        $count++;
        if ($count % 5 == 0) {
            echo "\n";
        }
    }
}

完整代码示例

将上述代码整合成一个完整的PHP脚本：

<?php
function isPrime($num) {
    if ($num <= 1) return false;
    if ($num == 2) return true;
    if ($num % 2 == 0) return false;
    for ($i = 3; $i <= sqrt($num); $i += 2) {
        if ($num % $i == 0) return false;
    }
    return true;
}

echo "1~100的素数有：\n";
$count = 0;
for ($i = 1; $i <= 100; $i++) {
    if (isPrime($i)) {
        echo str_pad($i, 3, " ", STR_PAD_LEFT);
        $count++;
        if ($count % 5 == 0) echo "\n";
    }
}
?>

算法优化思路

虽然上述方法已经可以正确判断素数，但在处理极大数字时效率可能不高。以下是几种优化方向：

预生成小素数：先存储小于√n的所有素数，只用这些素数去试除
6k±1法则：所有大于3的素数都可以表示为6k±1的形式
Miller-Rabin测试：概率性素数测试算法，适合大数判断

6k±1优化版本

function isPrimeOptimized($n) {
    if ($n <= 1) return false;
    if ($n <= 3) return true;
    if ($n % 2 == 0 || $n % 3 == 0) return false;
    for ($i = 5; $i * $i <= $n; $i += 6) {
        if ($n % $i == 0 || $n % ($i + 2) == 0) {
            return false;
        }
    }
    return true;
}

性能对比测试

我们可以比较两种算法的执行时间：

$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
    isPrime($i);
}
$time1 = microtime(true) - $start;

$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
    isPrimeOptimized($i);
}
$time2 = microtime(true) - $start;

echo "基础方法耗时：{$time1}秒\n";
echo "优化方法耗时：{$time2}秒\n";

实际应用场景

素数判断在以下领域有重要应用：

密码学：RSA加密算法依赖大素数的难以分解性
哈希算法：素数常用于设计散列函数
随机数生成：素数可以提高随机数质量

扩展练习

尝试编写一个函数，找出指定范围内的所有孪生素数（相差2的素数对）
实现埃拉托斯特尼筛法（Sieve of Eratosthenes）来找出一定范围内的所有素数
编写一个PHP脚本，输出前N个素数

总结

本文详细介绍了： - 素数的数学定义 - 素数判断的基本算法原理 - PHP实现素数判断的完整代码 - 打印1~100素数的多种格式 - 算法优化思路和性能对比 - 素数的实际应用价值

通过这个练习，我们不仅掌握了素数判断的方法，还学习了PHP的基本语法和算法优化思路。这些知识对于后续学习更复杂的算法和PHP开发都有重要意义。 “`