ホームページ > 記事 > バックエンド開発 > 素数を見つけるためのPHPスクリーニング方法

素数を見つけるためのPHPスクリーニング方法

不言オリジナル: 2018-05-31 17:10:262208ブラウズ

この記事では、主に素数を見つけるための PHP スクリーニング方法を紹介します。必要な友達に参考にしてください。まず、素数は、それ自身と 1 で割り切れる正の整数のみです。特に、1 は素数ではないと規定します。

分析:

まず、数値が素数かどうかを判断します:

私たちが行うことは、選択された数値を、現在の数値の平方根より小さいすべての数値で割ることです。均等に割れる場合は素数ではなく、そうでない場合は素数です。ここで重要なのは、なぜ平方根だけを使用するのかということです。

これは、数値が 2 つの数値の積に等しいとき、2 つの数値のうちの 1 つは数値の平方根より小さくなければならず、もう 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以内的素数

方法2: スクリーニング法を使用して素数を見つける

分析: スクリーニング法とは何ですか?これは次のようになります。まず、与えられた N 個の数値がすべて素数であると仮定し、最初の数値からフィルタリングを開始します。現在の数値倍数が倍数の場合、その倍数インジケーターを 0 に変更します。マークを付けた後、2 番目の数値を入力し、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 中国語 Web サイトを参照してください。

素数を見つけるためのPHPスクリーニング方法

関連記事