越简单越好!

php 求两个正整数的最大公约数

发表于 2007-08-29 10:50 | 511次阅读 0次点赞   PHP
求两个正整数的最大公约数采用的辗转相除法求解。
以下是辗转的算法:
 分别用m,n,r表示被除数、除数、余数。
 ①求m/n的余数r.
 ②若r=0,则n为最大公约数.若r≠0,执行第③步.
 ③将n的值放在m中,将r的值放在n中.
 ④返回重新执行第①步。
<br />
<?php
function go($m,$n) {
if($m<$n) {
   $a = $m;
   $m = $n;
   $n = $a;
}
$r = $m%$n;
if($r) {
   return go($n,$r);
} else {
   return $n;
}
}
$arr = array(100,32);
$result = go($arr[0],$arr[1]);
echo $result;
?>

返回顶部 ^