「一、最大公約數(shù)」
「1. 是什么：」
首先來(lái)回憶一下什么叫最大公約數(shù)：指兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)。比如60和24，60的約數(shù)有[1,2,3,4,5,6,10,12,15,20,30,60]，24的約數(shù)有[1,2,3,4,6,8,12,24]，他們共同的約數(shù)有[1,2,3,4,6,12]，共同約數(shù)中最大的是12，所以最大公約數(shù)就是12。
「2. 如何求最大公約數(shù)？」
在數(shù)學(xué)中，我們用分解質(zhì)因數(shù)和短除法來(lái)求解，如下圖，就是百度經(jīng)驗(yàn)上用短除法求最大公約數(shù)和最小公倍數(shù)的一個(gè)過(guò)程。
短除法那么用程序如何實(shí)現(xiàn)呢？
其實(shí)如果要用程序?qū)崿F(xiàn)短除法求解，可能不是那么簡(jiǎn)單。我們可以用另一種方法，叫做「輾轉(zhuǎn)相除法」，又叫「歐幾里得算法」。
「3. 歐幾里得算法求最大公約數(shù)：」
我們用(A, B)表示求A(較大的那個(gè)數(shù))和B(較小的那個(gè)數(shù))的最大公約數(shù)。歐幾里得算法的公式如下：
- 首先讓
A / B = C ~ D，如果余數(shù)D為0，那么B就是最大公約數(shù)； - 如果D不為0，那么就讓除數(shù)和余數(shù)繼續(xù)做上面的運(yùn)算，即
B / D = E ~ F，直到余數(shù)為0，此時(shí)的除數(shù)就是最大公約數(shù)。
歐幾里得算法求(60, 24)的最大公約數(shù)步驟如下：
60 / 24 = 2 ~ 12，所以(60, 24) = (24, 12)；
24 / 12 = 2 ~ 0，所以(60, 24) = (24, 12) = 12
「代碼實(shí)現(xiàn)：」
public static int euclid(int a, int b){
if (a == b){
return a;
}
int dividend = Math.max(a, b); // 被除數(shù)
int divisor = Math.min(a, b); // 除數(shù)
int remainder = dividend % divisor; // 余數(shù)
while (remainder != 0){
dividend = divisor;
divisor = remainder;
remainder = dividend % divisor;
}
return divisor;
}
「4. 更相減損術(shù)求最大公約數(shù)：」
這是九章算術(shù)里面的求最大公約數(shù)的方法，我們用(A, B)表示求A(較大的那個(gè)數(shù))和B(較小的那個(gè)數(shù))的最大公約數(shù)，其步驟如下：
- 首先判斷A和B是否都是偶數(shù)，如果是，同時(shí)用2約分，要記住這一步約掉了幾個(gè)2；
- 當(dāng)A和B不同時(shí)為偶數(shù)的時(shí)候，讓
A - B = C，當(dāng)B和C相等時(shí)，C再乘以第一步約掉的2，約掉了幾個(gè)就乘以幾個(gè)，結(jié)果就是最大公約數(shù)； - 如果B和C不相等，那就看B和C誰(shuí)更大，用更大的那個(gè)做被減數(shù)，更小的那個(gè)做減數(shù)，繼續(xù)相減，直到減數(shù)和差相等。
更相減損術(shù)求(60, 24)的最大公約數(shù)步驟如下：
60 / 2 / 2 = 15，24 / 2 / 2 = 6；
此時(shí)減數(shù)和差相等了，所以最大公約數(shù)就是3 * 2 * 2 = 12。
「代碼實(shí)現(xiàn)：」
public static int moreExclude(int a, int b){
if (a == b){
return a;
}
int minute = Math.max(a, b); // 被減數(shù)
int minus = Math.min(a, b); // 減數(shù)
int count = 0;
while (minute % 2 == 0 && minus % 2 == 0){
minute = minute / 2;
minus = minus / 2;
count ++;
}
int difference = minute - minus; // 差
while (difference != minus){
minute = Math.max(minus, difference);
minus = Math.min(minus, difference);
difference = minute - minus;
}
return (int) (Math.pow(2, count) * difference);
}
更相減損術(shù)代碼看起來(lái)更復(fù)雜，多了一個(gè)while循環(huán)，實(shí)際上在數(shù)字不是很大的情況下，效率可能差不多，因?yàn)橛?jì)算機(jī)做減法是比做除法更快的。但是當(dāng)數(shù)字很大時(shí)，顯然除法循環(huán)的次數(shù)更少，可以更快地得到結(jié)果。
「二、最小公倍數(shù)」
求出了最大公約數(shù)，求最小公倍數(shù)就很簡(jiǎn)單了，因?yàn)榇嬖谌缦鹿剑?/p>
假如(a, b)的最大公約數(shù)是m，那么最小公倍數(shù)n = a * b / m。所以，要求最小公倍數(shù)，可以先用上述方法求出最大公約數(shù)。
