最大公约数
最大公约数(Greatest Common Divisor,简写为G.C.D.;或Highest Common Factor,简写为H.C.F.),指某几个整数共有约数中最大的一个。
维基百科
百度百科
解法
- 列举法:各自列出约数,再找出最大的公约数。
- 素因数分解法:两数各作素因数分解,然后取出共有的项乘起来。
- 短除法
- 辗转相除法(欧几里德算法):常使用于直观上不容易判别公约数的场合。
php实现
1 2 3 4 5 6 7 8 9 10 11 12
| $gcd = gmp_gcd('12', '6'); echo $gcd . PHP_EOL; var_dump($gcd);
|
2. 辗转相除法(照抄的)
1 2 3 4 5 6 7 8
| function gcd($m, $n) { if($m == 0 || $n == 0) { return abs(max(abs($m), abs($n))); }
$r = $m % $n; return $r ? gcd($n, $r) : abs($n); }
|
Stein 算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| function gcd($m, $n) { if($m == 0 || $n == 0) { return abs(max(abs($m), abs($n))); } if($m % 2 == 0 && $n % 2 == 0) { return 2 * gcd($m / 2, $n / 2); } elseif($m % 2 == 0) { return gcd($m / 2, $n); } elseif($n % 2 == 0) { return gcd($m, $n / 2); } else { return gcd(($m + $n) / 2, ($m - $n) / 2); } }
|