最大公约数与最小公倍数

如果数 a 能被数 b 整除,a 就叫做 b 的倍数,b 就叫做 a 的约数。

几个整数中公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。

几个自然数公有的倍数,叫做这几个数的公倍数,其中最小的一个自然数,叫做这几个数的最小公倍数。

本文将使用欧几里德算法实现求两个数的最大公约数。

最大公约数

欧几里德算法,也称辗转相除法

定理: gcd(a, b) = gcd(b, a mod b) ( a > b 且 a mod b 不为 0 ) 即 a 和 b 的最大公约数等于 b 和 a % b 的最大公约数

证明:a 可以表示成 a = kb + r,则 r = a mod b

假设 x 是 a, b 的一个公约数,则有 x|a , x|b , 而 r = a - kb,因此 x|r 因此 x 也是( b, a mod b )的公约数 因此( a, b )和( b, a mod b )的公约数是一样的,其最大公约数也必然相等 得证:当 a % b 为 0 的时候, 则另一个数为最大公约数

1
2
3
4
5
6
int gcd(int a, int b) {
//如果a<b, 交换a b
if(a < b) int tmp = a, a = b, b = tmp;
//如果b为0则结束循环, 返回0, 否则计算b与a%b的gcd
return b == 0 ? a : gcd(b, a % b);
}

最小公倍数

假设求 x, y 的最小公倍数

1
公式: x * y = 最小公倍数 * 最大公约数