PHP筛选法求素数

不言原创: 2018-05-31 17:10:262252浏览

这篇文章主要介绍了关于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筛选法求素数

相关文章