php计算两个整数的最大公约数常用算法小结
发布时间：2022-07-31 04:44:15 所属栏目：PHP教程 来源：互联网
导读：这篇文章主要介绍了php计算两个整数的最大公约数常用算法,实例总结了求最大公约数的三种常用方法,具有一定参考借鉴价值,需要的朋友可以参考下 本文实例讲述了php计算两个整数的最大公约数常用算法。分享给大家供大家参考。具体如下： 代码如下:?php //计时，
|
这篇文章主要介绍了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程序设计有所帮助。 （编辑：济宁站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
