PHP screening method to find prime numbers

This article mainly introduces the PHP screening method to find prime numbers. It has a certain reference value. Now I share it with you. Friends in need can refer to it

First of all, a prime number is a positive integer that can only be divisible by itself and 1. What is particularly pointed out is that we stipulate that 1 is not a prime number.

Analysis:

First determine whether a number is a prime number:

We do this , divide the selected number by all numbers less than the square root of the current number. If one of them is divisible, it is not a prime number, otherwise it is a prime number. The key here is why just use the square root?

It is like this. It is not difficult to find that when a number is equal to the product of two numbers, then one of the two numbers must be less than the square root of the number, and the other number must be less than the square root of the number. It is definitely greater than the square root of this number. That is to say, when we find that the current number can be divisible by a number smaller than its square root, there is no need to divide another number larger than its square root, reduce the number of loops, and let the algorithm More concise.

Method 1: Ordinary method

Code implementation:

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

Method 2: Use filtering Method to find prime numbers

Analysis: What is the screening method? This is like this. First, we mark 1 as a prime number and 0 as a non-prime number. Assume that the N numbers given are all prime numbers, marked as 1

from the first number Start screening. When you encounter a multiple of the current number, change its multiple identification to 0. After marking, enter the second number and repeat the operation of the first number until the square root of N. The final identification is still 1, which is a prime number.

Code implementation:

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

?>

The above is the entire content of this article, thank you for reading. Please pay attention to the PHP Chinese website for more information!

Related recommendations:

Detailed explanation of a simple case of PHP array operation

php export file compression package ZipArchive

The above is the detailed content of PHP screening method to find prime numbers. For more information, please follow other related articles on the PHP Chinese website!