最大公约数和最小公倍数算法

欧几里德算法

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:

$gcd(a,b) = gcd(b,a\%b)$

该算法用C++语言描述为

1
2
3
4
5
int Gcd(int a, int b) {
if(b == 0)
return a;
return Gcd(b, a % b);
}

或者不使用递归

1
2
3
4
5
6
7
8
int Gcd(int a, int b) {
while(b != 0) {
int r = b;
b = a % b;
a = r;
}
return a;
}

在已经算出整数a、b的最大公约数的基础上,我们可以通过下面的公式来求出它们的最小公倍数:
$LCM(a,b)=\frac{a×b}{GCD(a,b)}$