php如何计算两个整数的最大公约数

这篇文章将为大家详细讲解有关php如何计算两个整数的最大公约数，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

具体如下：

<?php //计时，返回秒 function  microtime_float () {     list( $usec ,  $sec ) =  explode ( " " ,  microtime ());     return ((float) $usec  + (float) $sec ); } ////////////////////////////////////////// //欧几里得算法 function ojld($m, $n) {     if($m ==0 && $n == 0) {         return false;     }     if($n == 0) {         return $m;     }     while($n != 0){         $r = $m % $n;         $m = $n;         $n = $r;     }     return $m; } ////////////////////////////////////////// //基于最大公约数的定义 function baseDefine($m, $n) {     if($m ==0 && $n == 0) {         return false;     }     $min = min($m, $n);     while($min >= 1) {         if($m % $min == 0){             if($n % $min ==0) {                 return $min;             }         }         $min -= 1;     }     return $min; } //////////////////////////////////////////// //中学数学里面的计算方法 function 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 as $v) {         while($mt % $v == 0) {             $mz[] = $v;             $mt = $mt / $v;         }         $c = 1;         foreach($mz as $v) {             $c *= $v;             if($c == $m){                 break 2;             }         }     }     //n所有质因数     foreach($np as $v) {         while($nt % $v == 0) {             $nz[] = $v;             $nt = $nt / $v;         }         $c = 1;         foreach($nz as $v) {             $c *= $v;             if($c == $n){                 break 2;             }         }     }     //公因数     $jj = array_intersect($mz, $nz); //取交集     $gys = array();     //取出在俩数中出现次数最少的因数，去除多余的。     $c = 1; //记录数字出现的次数     $p = 0; //记录上一次出现的数字     sort($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 = ( count($mk) > count($nk) ) ? count($nk) : count($mk);         if($c > $k) {             unset($jj[$key]);         }     }     $count = 1;     foreach($jj as $value) {         $count *= $value;     }     return $count; } //求给定大于等于2的整数的连续质数序列 //埃拉托色尼筛选法 function getList($num) {     $a = array();     $a = array();     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++;         }     }     return $L; } ///////////////////////////////////// //test $time_start  =  microtime_float (); //echo ojld(60, 24);       //0.0000450611 seconds //echo baseDefine(60, 24); //0.0000557899 seconds echo baseSchool(60, 24);   //0.0003471375 seconds $time_end  =  microtime_float (); $time  =  $time_end  -  $time_start ; echo '<br>' . sprintf('%1.10f', $time) . 'seconds';

关于“php如何计算两个整数的最大公约数”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。