Méthode de filtrage PHP pour trouver des nombres premiers

Cet article présente principalement la méthode de filtrage PHP pour trouver les nombres premiers. Il a une certaine valeur de référence. Maintenant, je le partage avec vous. Les amis dans le besoin peuvent s'y référer

<.>

Tout d'abord, un nombre premier est un entier positif qui ne peut être divisé que par lui-même et 1. Ce qui est particulièrement souligné, c'est qu'on stipule que 1 n'est pas un nombre premier.

Analyse :

Déterminez d'abord si un nombre est un nombre premier :

Nous le faisons this , divisez le nombre sélectionné par tous les nombres inférieurs à la racine carrée du nombre actuel. Si l'un d'eux est divisible, ce n'est pas un nombre premier, sinon c'est un nombre premier. La clé ici est de savoir pourquoi utiliser simplement la racine carrée ?

C'est comme ça. Il n'est pas difficile de constater que lorsqu'un nombre est égal au produit de deux nombres, alors l'un des deux nombres doit être inférieur à la racine carrée de. le nombre, et l'autre nombre Il est nettement supérieur à la racine carrée de ce nombre, c'est-à-dire que lorsque l'on constate que le nombre actuel peut être divisible par un nombre inférieur à la racine carrée de , il n'est pas nécessaire de diviser un autre nombre supérieur à sa racine carrée. Cela réduit le nombre de boucles et permet à l'algorithme d'être plus concis.

Méthode 1 : Méthode ordinaire

Implémentation du code :

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

Méthode 2 : Utiliser la méthode de criblage pour trouver des nombres premiers

Analyse : Quelle est la méthode de criblage ? C'est comme ça. Tout d'abord, nous marquons 1 comme nombre premier et 0 comme nombre non premier. Supposons que les N nombres donnés soient tous des nombres premiers, marqués comme 1

de. le premier numéro Lancez le dépistage. Lorsque vous rencontrez un multiple du numéro actuel, changez son identification multiple à 0. Après marquage, saisissez le deuxième numéro et répétez l'opération du premier numéro jusqu'à la racine carrée de N. L'identification finale est toujours 1, qui est un nombre premier

Implémentation du code :

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

?>

Ce qui précède est l'intégralité du contenu de cet article, merci d'avoir lu. Veuillez prêter attention au site Web PHP chinois pour plus d'informations !

Recommandations associées :

Explication détaillée des cas simples de fonctionnement d'un tableau PHP

Package de compression de fichier d'exportation PHP ZipArchive

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!