最大公约数

最大公约数(Greatest Common Divisor,简写为G.C.D.;或Highest Common Factor,简写为H.C.F.),指某几个整数共有约数中最大的一个。
维基百科
百度百科

解法

  • 列举法:各自列出约数,再找出最大的公约数。
  • 素因数分解法:两数各作素因数分解,然后取出共有的项乘起来。
  • 短除法
  • 辗转相除法(欧几里德算法):常使用于直观上不容易判别公约数的场合。

php实现

1. gmp扩展的 gmp_gcd
1
2
3
4
5
6
7
8
9
10
11
12
// 需要注意一下gmp_gcd生成的是一个GMP对象
$gcd = gmp_gcd('12', '6');
echo $gcd . PHP_EOL;
var_dump($gcd);

/*
6
class GMP#1 (1) {
public $num =>
string(1) "6"
}
*/

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);
}
}