《php计算两个整数的最大公约数常用算法小结_.docx》由会员分享，可在线阅读，更多相关《php计算两个整数的最大公约数常用算法小结_.docx（8页珍藏版）》请在三一文库上搜索。
1、php计算两个整数的最大公约数常用算法小结_ 这篇文章主要介绍了php计算两个整数的最大公约数常用算法,实例总结了求最大公约数的三种常用方法,具有肯定参考借鉴价值,需要的伴侣可以参考下 本文实例讲解并描述了php计算两个整数的最大公约数常用算法。分享给大家供大家参考。具体如下： 代码如下: ?php /计时，返回秒 function microtime_float () list( $usec , $sec ) = explode ( , microtime (); return (float) $usec + (float) $sec ); / /欧几里得算法 function ojld($
2、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; /
3、 /中学数学里面的计算方法 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;
4、$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; /记录数
5、字消失的次数 $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 *= $va
6、lue; 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 !=
7、 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程序设计有所关心。 更多信息请查看IT技术专栏 .