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';