求一定范围内所有的素数（质数）的思路和方法- 开心博客

定义

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

问题

求2到100之间所有的素数

代码中，$num表示循环次数；通过num最终值，可以判断哪个算法更好。

方法

1. 易理解版本
分析：两层循环，取外层大循环的值与小于其值的所有数，取余数；等于0，则表示能被小值整除，说明不是素数。
代码：

$num = 0;
for ($i = 2;$i <= 100;$i++){
    $is = true;
    for ($j = 2;$j < $i;$j++){
        if ($i % $j == 0){
            //能被整除,不是素数
            $is = false;
            break;
        }
        $num++;
    }
    if ($is){
        echo $i.' ';
    }
}
echo '<br/>循环次数：'.$num;

结果：

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
循环次数：1059

2. 优化版
分析：既然不能被其他数整除，那么肯定也不能被他的一半整除（更没必要继续判断大于一半的值能否被整除），否则就不是素数。这样，我们就可以将方法1的循环减半，只循环到n的一半，然后判断是否能被整除即可。能，则不是素数；不能，则是素数；

$num = 0;
for ($i=2; $i < 100; $i++) {
    for ($j=2; $j <= $i/$j; $j++) {
        $num++;
        if($i%$j==0) {
            break; // 如果发现因子，则不是素数
        }
    }
    if($j > ($i/$j)) {
        echo($i." " );
    }
}
echo '<br/>循环次数：'.$num;

结果：

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
循环次数：235

3. 精简优化版
分析：我们知道，偶数一定不是素数，即 n%2!=0

$num = 0;
for ($i=2; $i < 100; $i++) {
    for ($j=2; ($j <= ($i/$j)) && ($i % 2 != 0); $j++) {
        $num++;
        if($i%$j==0) {
            break; // 如果发现因子，则不是素数
        }
    }
    if($j > ($i/$j)) {
        echo($i." " );
    }
}
echo '<br/>循环次数：'.$num;

结果：

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
循环次数：187

总结

从循环次数，可以很明显看出，第三种方法是最高效的。