GCD&LCM-求最大公约数&最小公倍数

1. 定义

最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。
最小公倍数（Least Common Multiple，缩写L.C.M.），如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数，对于两个整数来说，指该两数共有倍数中最小的一个。计算最小公倍数时，通常会借助最大公约数来辅助计算。

2. 辗转相除法（欧几里德算法）求最大公约数

核心：
把上一轮有余数的除法计算中， 除数变为下一轮计算的被除数， 余数变为下一轮计算的除数， 一直这样计算下去， 直到最后一次计算余数为零， 在最后一轮计算中的被除数，即为所求的最大公约数
算法实现：

//dividend:被除数，两者之间较大的数
//divisor：除数，两者之间较小的数
int GCD(int dividend, int divisor) ;
int GCD(int dividend, int divisor)  
{
int temp;
while (divisor>0)
 {
  temp = dividend % divisor;
  dividend = divisor;
  divisor = temp;
 }
return dividend;
}

3. 最小公倍数

最小公倍数常常借助于最大公约数的计算——最小公倍数等于两数之积除以其最大公约数

//dividend:被除数，两者之间较大的数
//divisor：除数，两者之间较小的数
int LCM(int dividend, int divisor) ;
int LCM(int dividend, int divisor)
{ 
return dividend*divisor/GCD(dividend, divisor);
}