PHP篩選法求質數

不言原創: 2018-05-31 17:10:262247瀏覽

這篇文章主要介紹了關於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篩選法求質數

相關文章