最大公约数

最大公约数（英语：greatest common divisor，gcd）是指能够整除多个整数的最大正整数。而多个整数不能都为零。例如 8 和 12 的最大公约数为4。整数 $a$ , $b$ 的最大公约数记为 $gcd(a, b)$。

解法

枚举法

这是最简单也最容易想到的方法，即将所有数的约数都罗列出来，然后再比较找到最大公约数，如 8 和 12 的约数分别为：

8的约数：1、2、4、8

12的约数：1、2、3、4、6、12

最大公约数：4

算法实现：

质因数分解法

分别列出两数的素因数分解式，并计算共同项的乘积，如 8 和 12 的约数分别为：

8的素因数分解式为：**2 * 2 *** 2

12的素因数分解式为：**2 * 2 *** 3

共同项乘积：2 * 2

算法实现：

短除法

两数除以其共同 素因数 ，直到两数 互素 时，所有除数的乘积即为最大公约数。

辗转相除法

也称为欧几里得算法，相对前面几种方法，这种算法要更高效。