PHP筛选法求素数

PHP筛选法求素数,第1张

这篇文章主要介绍了关于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导出文件压缩包 ZipArchive

以上就是PHP筛选法求素数 的详细内容,更多请关注php中文网其它相关文章!

文章来源:https://www.php.cn/faq/399576.html

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复