php计算两个整数的最大公约数常用算法小结
本文实例讲述了php计算两个整数的最大公约数常用算法。分享给大家供大家参考。具体如下：
<?php
//计时，返回秒
function microtime_float()
{
list($usec, $sec)= explode("", microtime());
return((float)$usec +(float)$sec);
}
//////////////////////////////////////////
//欧几里得算法
functionojld($m,$n){
if($m==0&&$n==0){
returnfalse;
}
if($n==0){
return$m;
}
while($n!=0){
$r=$m%$n;
$m=$n;
$n=$r;
}
return$m;
}
//////////////////////////////////////////
//基于最大公约数的定义
functionbaseDefine($m,$n){
if($m==0&&$n==0){
returnfalse;
}
$min=min($m,$n);
while($min>=1){
if($m%$min==0){
if($n%$min==0){
return$min;
}
}
$min-=1;
}
return$min;
}
////////////////////////////////////////////
//中学数学里面的计算方法
functionbaseSchool($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($mpas$v){
while($mt%$v==0){
$mz[]=$v;
$mt=$mt/$v;
}
$c=1;
foreach($mzas$v){
$c*=$v;
if($c==$m){
break2;
}
}
}
//n所有质因数
foreach($npas$v){
while($nt%$v==0){
$nz[]=$v;
$nt=$nt/$v;
}
$c=1;
foreach($nzas$v){
$c*=$v;
if($c==$n){
break2;
}
}
}
//公因数
$jj=array_intersect($mz,$nz);//取交集
$gys=array();
//取出在俩数中出现次数最少的因数，去除多余的。
$c=1;//记录数字出现的次数
$p=0;//记录上一次出现的数字
sort($jj);
foreach($jjas$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($jjas$value){
$count*=$value;
}
return$count;
}
//求给定大于等于2的整数的连续质数序列
//埃拉托色尼筛选法
functiongetList($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();
//echoojld(60,24); //0.0000450611seconds
//echobaseDefine(60,24);//0.0000557899seconds
echobaseSchool(60,24); //0.0003471375seconds
$time_end = microtime_float();
$time = $time_end - $time_start;
echo'<br>'.sprintf('%1.10f',$time).'seconds';
希望本文所述对大家的php程序设计有所帮助。