PHP-Screening-Methode zum Finden von Primzahlen

Dieser Artikel stellt hauptsächlich die PHP-Screening-Methode zum Finden von Primzahlen vor. Jetzt kann ich ihn mit allen teilen, die ihn benötigen

Zuallererst ist eine Primzahl eine positive ganze Zahl, die nur durch sich selbst und 1 geteilt werden kann. Besonders hervorzuheben ist, dass wir festlegen dass 1 keine Primzahl ist.

Analyse:

Bestimmen Sie zunächst, ob eine Zahl eine Primzahl ist:

Das tun wir Teilen Sie die ausgewählte Zahl durch alle Zahlen, die kleiner als die Quadratwurzel der aktuellen Zahl sind. Wenn eine davon teilbar ist, ist sie keine Primzahl, andernfalls ist sie eine Primzahl. Der Schlüssel hier ist, warum einfach die Quadratwurzel verwenden?

Es ist nicht schwer herauszufinden, dass eine der beiden Zahlen kleiner als die Quadratwurzel sein muss, wenn eine Zahl gleich dem Produkt zweier Zahlen ist Die Zahl und die andere Zahl sind definitiv größer als die Quadratwurzel dieser Zahl. Das heißt, wenn wir feststellen, dass die aktuelle Zahl durch eine Zahl kleiner als die Quadratwurzel von teilbar ist, Es ist nicht erforderlich, eine andere Zahl zu dividieren, die größer als ihre Quadratwurzel ist. Dies reduziert die Anzahl der Schleifen und ermöglicht eine präzisere Ausführung des Algorithmus.

Methode 1: Gewöhnliche Methode

Code-Implementierung:

<?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以内的素数

Methode 2: Filterung verwenden Methode zum Finden von Primzahlen

Analyse: Was ist die Screening-Methode? Das ist so. Zuerst markieren wir 1 als Primzahl und 0 als Nicht-Primzahl. Nehmen wir an, dass die angegebenen N-Zahlen alle Primzahlen sind, markiert als 1

von die erste Zahl. Beginnen Sie mit dem Screening. Wenn Sie auf ein Vielfaches der aktuellen Zahl stoßen, ändern Sie deren Vielfachidentifikation auf 0. Geben Sie nach dem Markieren die zweite Zahl ein und wiederholen Sie den Vorgang der ersten Zahl, bis die Quadratwurzel von N erreicht ist. Die endgültige Identifikation ist still 1, was eine Primzahl ist

Code-Implementierung:

<?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) ;

?>

Das Obige ist der gesamte Inhalt dieses Artikels, vielen Dank fürs Lesen. Weitere Informationen finden Sie auf der chinesischen PHP-Website!

Verwandte Empfehlungen:

Detaillierte Erklärung einfacher Fälle von PHP-Array-Operationen

PHP-Exportdateikomprimierungspaket ZipArchive

Das obige ist der detaillierte Inhalt vonPHP-Screening-Methode zum Finden von Primzahlen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!