这篇文章主要介绍了关于PHP筛选法求素数 ，有着一定的参考价值，现在分享给大家，有需要的朋友可以参考一下
首先，素数是只能被自己和1整除的正整数,特别指出的是我们规定1不是素数。
分析：
首先判断一个数是不是素数：
我们这样做的，用选定的这个数除以小于当前这个数的平方根的所有的数，如果有一个能整除，则不是素数，否则素数。这里的关键是为何只用是平方根就行呢？
是这样的，不难发现，当一个数等于两个数的乘积时，那么这两个数中必然有一个要小于这个数的平方根，另外一个数肯定大于这个数的平方根，也就说当我们发现当前数能被比他平方根小的数整除，就不用去整除另一个比他平方根大的数，减少循环次数，让算法更简洁。
方法一：普通方法
代码实现：
<?php
function sushu($n) {
for($j=2;$j<=$n;++$j){
for($i=2,$sqrt=sqrt($j);$i<=$sqrt;++$i){ //只用判定当前数的平方根
if($j%$i==0){
continue 2; //如果不是素数，则跳出内层循环，从外层循环继续执行
}
}
echo $j;
echo "<br>";
}
}
sushu(100); ?> //100以内的素数方法二：利用筛选法求素数
分析：何为筛选法呢？是这样的，首先我们把1标识成素数，把0标识成非素数，假设给出的N个数都是素数，标识为1
从第一个数开始筛选，遇到当前这个数的倍数就把他的倍数标识改为0，标识完后再进入第二个数重复第一个数的操作，直到N的平方根，最后标识仍然为1的就是素数
代码实现：
<?php
function sushu1($n) {
$arr=array_fill(2,$n-1,1);//填充一个下标从2开始，共$n-1个元素，值为1的数组
for($i=2,$sqrt=sqrt($n);$i<=$sqrt;++$i){ //筛选范围
if($arr[$i]==1){ //选定筛选数
for($j=2*$i;$j<=$n;$j+=$i){ //所有筛选数的倍数的值置为0
$arr[$j]=0;
}
}
}
foreach($arr as $key=>$value){ //遍历数组
if($value==1){
echo $key; //值为1的下标取出，就是素数
echo "<br>";
}
}
}
sushu1(100) ;
?>以上就是本篇文章的全部内容了，感谢大家阅读。更多请关注PHP中文网！
相关推荐：
以上是PHP筛选法求素数 的详细内容。更多信息请关注PHP中文网其他相关文章！
