什么是素数？

素数（Prime Number）指的是大于1的自然数中，除了1和它自身以外，不再有其他因数的数。换句话说，一个素数只能被1和它自己整除。

举个例子：2、3、5、7、11、13、17、19、23……这些都是素数。其中2是个特殊的存在——它是唯一的偶数素数。

这里有个容易混淆的点：0和1不是素数，因为素数定义要求大于1。很多新手刚开始会搞错这一点，我自己当初学的时候也在这里踩过坑。

核心判定原理

判断一个数是否为素数，基本的数学思路是：检查从2到该数减1之间，是否存在能整除它的数。如果存在，说明它不是素数；如果不存在，那它就是素数。

不过这种写法在开发中效率并不好。后面我会讲一下为什么很多有经验的开发者不会直接这么写。

示例一：输出前15个素数

下面用PHP实现一个简单脚本，依次找出前15个素数并打印出来。

<?php  
$count = 0;      // 已经找到的素数个数
$num = 2;        // 从2开始检查

while ($count < 15) {  
    $div_count = 0;   // 每次重置因数计数器
    
    // 检查$num有多少个因数
    for ($i = 1; $i <= $num; $i++) {  
        if (($num % $i) == 0) {  
            $div_count++;  
        }  
    }  
    
    // 素数的因数只有两个：1和自身
    if ($div_count < 3) {  
        echo $num . " , ";  
        $count = $count + 1;  
    }  
    $num = $num + 1;  
}  
?>

运行结果：2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47

个人经验：上面这个写法逻辑清楚，适合教学场景，但在项目中我不会这样用。原因很简单——效率问题。每次循环都要从1遍历到$num，当数字变大时运算量会急剧增加。比如判断999983是不是素数，这个算法就得循环近百万次。后面我会给出更实用的改进思路。

示例二：表单提交判断素数

用户通过表单输入一个数字，程序返回判断结果。

<form method="post">  
    请输入一个数字：<input type="text" name="input"><br><br>  
    <input type="submit" name="submit" value="提交判断">  
</form>  

<?php  
if ($_POST) {  
    $input = $_POST['input'];  
    
    // 过滤非数字输入
    if (!is_numeric($input) || $input <= 1) {
        echo '请输入大于1的有效整数';
        return;
    }
    
    $is_prime = true;  
    for ($i = 2; $i <= $input - 1; $i++) {  
        if ($input % $i == 0) {  
            $is_prime = false;  
            break;   // 找到一个因数就可以提前终止了
        }  
    }  
    
    if ($is_prime) {  
        echo '数字 ' . $input . ' 是素数';  
    } else {  
        echo '数字 ' . $input . ' 不是素数';  
    }   
}  
?>

本节课程知识要点

项目开发中的改进写法

前面提到基础写法效率偏低，这里说一个常见的优化技巧：检查范围只需要到√n（平方根）即可。

因为如果一个数n能被某个大于√n的数整除，那么商一定小于√n，这个较小的因数早就被检查过了。所以循环到√n就够了。

function isPrime($num) {
    if ($num <= 1) return false;
    if ($num == 2) return true;
    if ($num % 2 == 0) return false;  // 排除偶数
    
    $limit = (int)sqrt($num);
    for ($i = 3; $i <= $limit; $i += 2) {  // 只检查奇数
        if ($num % $i == 0) return false;
    }
    return true;
}

改动说明：

• 先单独处理2和偶数情况

• 循环只检查奇数因数

• 循环上限设为平方根

这个函数在判断大数时性能会好很多。比如判断一百万左右的数，优化前可能要做近百万次取模运算，优化后只需要一千次左右。

常见面试题扩展

在代码面试中，经常会遇到这样的变体问题：

1. 输出100以内的所有素数：在上面代码基础上修改while条件即可

2. 判断输入是否为素数并返回因数列表：需要记录所有能整除的数

3. 求两个数之间的所有素数：在外层加个区间遍历

专业术语：筛法（Sieve Method） 是批量生成素数时更高效的算法，其中埃拉托斯特尼筛法（Sieve of Eratosthenes） 是经典实现，适合一次性生成一定范围内的素数。

个人建议

初学阶段掌握最基础的循环取模写法没问题，但理解原理之后，建议尽早接触平方根优化和筛法。另外表单场景一定要做输入校验——用户可能输入负数、小数、甚至是空值，这些都需要妥善处理，否则程序会出警告或报错。