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>)
 {
  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);
}