最大公約數(shù)(GCD, Greatest Common Divisor，為簡便下文都使用GCD表示最大公約數(shù))：指某幾個整數(shù)共有約數(shù)中最大的一個懂傀。
由于多個數(shù)的GCD可以拆分成兩個數(shù)的GCD芬骄，所以一般來說常見的是求兩個數(shù)的GCD翠忠。廢話不多說狠半，來看看目前我已知的求GCD的方法可缚。
- 窮舉法
- 輾轉(zhuǎn)相除法
- 輾轉(zhuǎn)相減法
下面來一個一個看穴墅。約定待求GCD的數(shù)為a, b惶室。
1. 窮舉法
這是最容易想到，而且是最直接的方法玄货。簡言之皇钞，就是從1開始，到a,b中比較小的那個結(jié)束松捉，看能不能同時被a, b整除（如果能即為公約數(shù)）夹界，這樣一個循環(huán)下來一定可以找出GCD。
代碼如下：
// 窮舉法
public static int gcd_enumeration(int a, int b){
// 先找出a,b中小的那個
int smaller = a;
if (b < a) {
smaller = b;
}
int gcd = 1;
for (int i = 2; i <= smaller; i++) {
// 如果能同時被a和b除盡隘世，則更新GCD
if ((a % i == 0) && (b % i == 0)) {
gcd = i;
}
}
return gcd;
}
2. 輾轉(zhuǎn)相除法
輾轉(zhuǎn)相除法又稱為歐幾里得算法可柿，大概公元前300年歐幾里得老大爺就想出來這么個算法了，厲害了丙者！
該方法依托于一個定理：
gcd(a, b) = gcd(b, a mod b)
其中复斥，a mod b是a除以b所得的余數(shù)。
啥意思呢械媒，就是說a,b的最大公約數(shù)就是b,a mod b的最大公約數(shù)目锭。
證明如下：
(1)充分性：
設(shè)g是a,b的公約數(shù)，則a,b可由g來表示：
a = xg, b = yg (x,y為整數(shù))
又纷捞，a可由b表示（任意一個數(shù)都可以由另一個數(shù)來表示）：
a = kb + r (k為整數(shù)痢虹，r為a除以b所得余數(shù))
=> r = a - kb = xg - kyg = (x - ky)g
即，g也是r的約數(shù)主儡。
這樣奖唯，g就是(b, r)即(b, a mod b)的公約數(shù)。
(2)必要性：
設(shè)g是(b, a mod b)的公約數(shù)缀辩，類似于(1)臭埋，同樣可以推出g也是(a, b)的公約數(shù)踪央。
綜合(1)(2)可得(a, b)和(b, a mod b)的公約數(shù)是一樣的，當(dāng)然最大公約數(shù)也是一樣的瓢阴。
好了畅蹂，有了理論基礎(chǔ)，下面總結(jié)成算法步驟：
- a % b得余數(shù)r
- 若r == 0荣恐，則b即為GCD
- 若r != 0液斜，則a = b, b = r，返回步驟1
代碼如下
// 輾轉(zhuǎn)相除法（遞歸寫法）
public static int gcd_division_recursive(int a, int b){
if (b == 0) {
return a;
}
return gcd_division_recursive(b, a % b);
}
// 輾轉(zhuǎn)相除法（迭代寫法）
public static int gcd_division_iteration(int a, int b){
while(b != 0){// 為什么用b判斷呢叠穆？因為b就是用來存a%b的少漆，即上面算法步驟里的r的
int t = b;
b = a % b;
a = t;
}
return a;
}
3. 輾轉(zhuǎn)相減法
這個方法出處目前我也不知道，而且證明過程我也不知道硼被，先寫在這里示损，過后待我研究研究。
算法步驟：
- 若a > b嚷硫，則a = a - b
- 若b > a检访，則b = b - a
- 若a == b，則a(或b)即為最大公約數(shù)
- 若a != b仔掸，則回到1
既然沒有證明脆贵，那就舉個栗子瞧瞧看吧。
求32,12的最大公約數(shù)：
32 - 12 = 20 (20 > 12)
20 - 12 = 8 (8 < 12)
12 - 8 = 4 (4 < 8)
8 - 4 = 4 (4 == 4)
所以最大公約數(shù)是4.
代碼如下：
// 輾轉(zhuǎn)相減法（遞歸寫法）
public static int gcd_substract_recursive(int a, int b){
if(a == b)
return a;
return a > b ? gcd_substract_recursive(a - b, b) : gcd_substract_recursive(a, b - a);
}
// 輾轉(zhuǎn)相減法（迭代寫法）
public static int gcd_substract_iteration(int a, int b){
// 如果a,b不相等起暮，則用大的數(shù)減去小的數(shù)卖氨，直到相等為止
while(a != b){
if(a > b)
a = a - b;
else
b = b - a;
}
return a;
}
以上，我們知道了怎么求兩個數(shù)的最大公約數(shù)负懦，那最小公倍數(shù)呢筒捺？
其實，只要知道了a,b的最大公約數(shù)密似，那最小公倍數(shù)不就是a * b / gcd(a, b)嗎焙矛？
