>  기사  >  백엔드 개발  >  소수를 찾는 PHP 스크리닝 방법

소수를 찾는 PHP 스크리닝 방법

不言
不言원래의
2018-05-31 17:10:262216검색

이 글에서는 소수를 찾는 PHP 스크리닝 방법을 주로 소개합니다. 이제 특정 참조 값을 가지고 있으므로 도움이 필요한 친구들이 참고할 수 있습니다.

먼저, 소수는 자신과 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: 선별 방법을 사용하여 소수 찾기

분석: 선별 방법이란 무엇인가요? 먼저 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 배열 작업의 간단한 사례에 대한 자세한 설명

php 내보내기 파일 압축 패키지 ZipArchive

위 내용은 소수를 찾는 PHP 스크리닝 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.