php如何计算两个整数的较大公约数-创新互联
这篇文章将为大家详细讲解有关php如何计算两个整数的较大公约数,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。
成都创新互联公司服务项目包括三都网站建设、三都网站制作、三都网页制作以及三都网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,三都网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到三都省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!具体如下:
= 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 '
' . sprintf('%1.10f', $time) . 'seconds';
关于“php如何计算两个整数的较大公约数”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。
文章名称:php如何计算两个整数的较大公约数-创新互联
链接地址:http://scyanting.com/article/dcsejj.html