PHP_php 팁에서 두 정수의 최대 공약수를 계산하는 일반적인 알고리즘 요약

이 기사의 예에서는 PHP에서 두 정수의 최대 공약수를 계산하는 공통 알고리즘을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 세부 내용은 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

//타이머, 초 반환
함수 microtime_float()
{
list( $usec , $sec ) = 폭발( " " , 마이크로타임());
반환 ((float) $usec (float) $sec );
}
//////////////////////////////////////////
//유클리드 알고리즘
함수 ojld($m, $n) {
If($m ==0 && $n == 0) {
         false를 반환합니다.
}
If($n == 0) {
         $m 반환
}
동안($n != 0){
          $r = $m % $n;
          $m = $n;
          $n = $r;
}
$m 반환;
}
//////////////////////////////////////////
//최대공약수를 기준으로 한 정의
함수 baseDefine($m, $n) {
If($m ==0 && $n == 0) {
         false를 반환합니다.
}
$min = min($m, $n);
동안($min >= 1) {
If($m % $min == 0){
                  if($n % $min ==0) {
                      $min 반환;
            }
}
         $min -= 1;
}
$min 반환;
}
////////////////////////////////////////////
//중학교 수학의 계산방법
함수 baseSchool($m, $n) {
$mp = getList($m); //$m보다 작은 모든 소수
$np = getList($n); //$n보다 작은 모든 소수
$mz = array(); //$m의 소인수를 저장합니다
$nz = array(); //$n의 소인수를 저장합니다
$mt = $m;
$nt = $n;
//m모든 소인수
//m의 모든 소수를 순회합니다. m으로 나누어질 수 있으면 다음 나눗셈을 계속합니다. 만약 m으로 나누어질 수 있는 다음 소수를 취합니다.
//소수, 나타나는 모든 소수의 곱이 m과 같을 때 중지
foreach($mp를 $v로) {
​​​​while($mt % $v == 0) {
               $mz[] = $v;
               $mt = $mt / $v;
}
         $c = 1;
foreach($mz를 $v로) {
               $c *= $v;
                if($c == $m){
휴식 2;
            }
}
}
//n의 모든 소인수
foreach($np를 $v로) {
​​​​while($nt % $v == 0) {
                 $nz[] = $v;
                $nt = $nt / $v;
}
         $c = 1;
foreach($nz를 $v로) {
               $c *= $v;
                if($c == $n){
휴식 2;
            }
}
}
//공통인수
$jj = array_intersect($mz, $nz); //교차점 구하기
$gys = 배열();
//두 숫자 중 가장 적게 나타나는 요소를 구하고 중복되는 요소를 제거합니다.
$c = 1; //숫자가 나타나는 횟수를 기록합니다
$p = 0; //마지막으로 나타난 숫자를 기록합니다
정렬($jj);
foreach($jj as $key => $v) {
If($v == $p) {
                 $c ;
}
        elseif($p != 0) {
              $c = 1;
}
          $p = $v;
          $mk = array_keys($mz, $v);
          $nk = array_keys($nz, $v);
            $k = ( 개수($mk) > 개수($nk) ) ? 개수($nk) : 개수($mk);
If($c > $k) {
               unset($jj[$key]);
}
}
$count = 1;
foreach($jj를 $value로) {
         $count *= $value;
}
$count 반환;
}
//2보다 크거나 같은 주어진 정수에 대해 연속된 소수의 시퀀스를 찾습니다
//에라토스테네스 스크리닝 방법
함수 getList($num) {
$a = 배열();
$a = 배열();
for($i = 2; $i <= $num; $i ) {
          $a[$i] = $i;
}
for( $i = 2; $i <= Floor( sqrt($num) ); $i ) {
If($a[$i] != 0) {
               $j = $i * $i;
              while($j <= $num) {
                     $a[$j] = 0;
                    $j = $j $i;
            }
}
}
$p = 0;
for($i = 2; $i <= $num; $i ) {
If($a[$i] != 0) {
               $L[$p] = $a[$i];
               $p ;
}
}
$L 반환;
}
//////////////////////////////////////
//테스트
$time_start = 마이크로타임_플로트();
//echo ojld(60, 24); //0.0000450611초
//echo baseDefine(60, 24); //0.0000557899초
echo baseSchool(60, 24); //0.0003471375초
$time_end = 마이크로타임_플로트();
$time = $time_end - $time_start ;
echo '
' . sprintf('%1.10f', $time) .

이 기사가 모든 사람의 PHP 프로그래밍 설계에 도움이 되기를 바랍니다.