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

发表于   |   分类于   |  

欧几里德算法

欧几里德算法又称辗转相除法，用于计算两个整数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)}$