一、前言

嘿，小傅哥怎么突然講到最大公約數(shù)了？

這么想你肯定是沒(méi)有好好閱讀前面章節(jié)中小傅哥講到的RSA算法，對(duì)于與歐拉結(jié)果計(jì)算的互為質(zhì)數(shù)的公鑰e，其實(shí)就需要使用到輾轉(zhuǎn)相除法來(lái)計(jì)算出最大公約數(shù)。

放心，你所有寫(xiě)的代碼，都是對(duì)數(shù)學(xué)邏輯的具體實(shí)現(xiàn)，無(wú)非是難易不同罷了。所以如果你真的想學(xué)好編程思維而不只是CRUD，那就要把數(shù)據(jù)結(jié)構(gòu)、算法邏輯等根基打牢。

二、短除法

既然都說(shuō)到這了，那你還記得怎么計(jì)算最大公約數(shù)嗎，死鬼？

以上這種方式就是我們?cè)谏蠈W(xué)階段學(xué)習(xí)的，這種計(jì)算方式叫做短除法。

短除法：是算術(shù)中除法的算法，將除法轉(zhuǎn)換成一連串的運(yùn)算。短除法是由長(zhǎng)除法簡(jiǎn)化而來(lái)，當(dāng)中會(huì)用到心算，因此除數(shù)較小的除法比較適用短除法。對(duì)大部分的人而言，若除以12或12以下的數(shù)，可以用記憶中乘法表的內(nèi)容，用心算來(lái)進(jìn)行短除法。也有些人可以處理除數(shù)更大的短除法?！?來(lái)自維基百科

三、歐幾里德算法

短除法能解決計(jì)算最大公約數(shù)的問(wèn)題，但放到程序編寫(xiě)中總是很別扭，總不能一個(gè)個(gè)數(shù)字去試算，這就顯得很鬧挺。其實(shí)除了短除法還有一種是計(jì)算公約數(shù)的辦法，叫做歐幾里德算法。

歐幾里德算法：是計(jì)算兩個(gè)整數(shù)（數(shù)字）的最大公約數(shù)【GCD(Greatest Common Divisor)】的有效方法，即能將它們整除而無(wú)余數(shù)的最大數(shù)。它以古希臘數(shù)學(xué)家 歐幾里得的名字命名，歐幾里德在他的幾何原本（約公元前 300 年）中首次描述了它。它是算法的示例，是根據(jù)明確定義的規(guī)則執(zhí)行計(jì)算的分步過(guò)程，并且是常用的最古老的算法之一。它可以用來(lái)減少分?jǐn)?shù)到他們的最簡(jiǎn)單的形式，并且是許多其他數(shù)論和密碼計(jì)算的一部分?！?來(lái)自維基百科

GCD，代表了兩個(gè)數(shù)字的最大公約數(shù)，GCD(X,Y) = Z，那么就表示 X 和 Y 的最大公約數(shù)是 Z。由歐幾里德算法給出 GCD(X,Y) = GCD(Y,XmodY) —— mod 表示求模計(jì)算余數(shù)。

其實(shí)簡(jiǎn)單來(lái)說(shuō)就是，X和Y的公約數(shù)是Z，那么Y和Z的公約數(shù)也是Z。24和18的最大公約數(shù)是6，那么18和6的公約數(shù)也是6。嘿，就這么一個(gè)事。但就因?yàn)橛辛诉@一樣一條推論，讓編程代碼變得優(yōu)雅舒服，只需要不斷地將X、Y兩數(shù)作差，就能計(jì)算最大公約數(shù)。

這讓小傅哥想起，多年前上學(xué)時(shí)候，我也給出過(guò)一條推論；”任意一組所能構(gòu)成等差數(shù)列的三個(gè)數(shù)字，所能組合出來(lái)的一個(gè)三位數(shù)，都能被3整除?！?例如：等差數(shù)列 16、31、46 組合成三位數(shù) 463116 或者 461631 都能被3整除。

四、輾轉(zhuǎn)相除法代碼實(shí)現(xiàn)

歐幾里德算法 = 輾轉(zhuǎn)相除法法：https://en.wikipedia.org/wiki/Euclidean_algorithm

在輾轉(zhuǎn)相除法的實(shí)現(xiàn)中，計(jì)算最大公約數(shù)的方式，就是使用一個(gè)數(shù)字減去另外一個(gè)數(shù)字，直到兩個(gè)數(shù)字相同或者有其中一個(gè)數(shù)字為0，那么最后不為零的那個(gè)數(shù)字就是兩數(shù)的最大公約數(shù)。

小傅哥在這里提供了2種計(jì)算方式，一種是循環(huán)另外一種是遞歸?！?方便很多看不懂遞歸的小伙伴可以用另外的方式學(xué)習(xí)。

1. 循環(huán)實(shí)現(xiàn)

public long gcd01(long m, long n){
    m = Math.abs(m);
    n = Math.abs(n);
    
    while (m != 0 && n != 0 && m != n) {
        if (m > n) {
            m = m - n;
        } else {
            n = n - m;
        }
    }
    return m == 0 ? n : m;
}

• 兩數(shù)循環(huán)處理中，條件為 m != 0 && n != 0 && m != n直至循環(huán)結(jié)束。

2. 遞歸實(shí)現(xiàn)

public long gcd02(long m, long n){
    if (m < n) {
        long k = m;
        m = n;
        n = k;
    }
    if (m % n != 0) {
        long temp = m % n;
        return gcd02(n, temp);
    } else {
        return n;
    }
}

• 計(jì)算方式邏輯和條件是一樣的，只不過(guò)這個(gè)是使用了遞歸調(diào)用的方式進(jìn)行處理。

3. 測(cè)試驗(yàn)證

@Test
public void test_euclidean() {
    Euclidean euclidean = new Euclidean();
    System.out.println(euclidean.gcd01(124, 20));
    System.out.println(euclidean.gcd02(124, 20));
}

測(cè)試結(jié)果

4
4


Process finished with exit code 0

• 計(jì)算 124 和 20 的最大公約數(shù)，兩個(gè)計(jì)算方式結(jié)果都是 4 。好的，到這測(cè)試通過(guò)。
• 這并不是一個(gè)很難的知識(shí)點(diǎn)，但當(dāng)你做一些技術(shù)分享、答辯述職等時(shí)候，能這樣用技術(shù)語(yǔ)言而不是大白話(huà)的講述出來(lái)后，其實(shí)高度就有了。兄弟！

在 stackoverflow.com 看到一道問(wèn)題：計(jì)算兩個(gè)整數(shù)的最小公倍數(shù)的最有效方法是什么？

乍一看， 這能有啥。不就是計(jì)算下最小公倍數(shù)嗎？但一想我腦袋中計(jì)算最小公倍數(shù)的方法；一種是在本子上通過(guò)短除法計(jì)算，另外一種是基于計(jì)算出的最大公約數(shù)，再使用公式：lcm(a, b) = |a * b| / gcd(a, b) 求得最小公倍數(shù)?！?計(jì)算最大公約數(shù)是基于歐幾里德算法(輾轉(zhuǎn)相除法)

那么這樣的計(jì)算方法是不是最有效的方法，另外如果是同時(shí)計(jì)算多個(gè)整數(shù)的最小公倍數(shù)，要怎么處理？

其實(shí)編程的學(xué)習(xí)往往就是這樣，留心處處都是學(xué)問(wèn)，你總是需要從各種細(xì)小的點(diǎn)中，積累自己的技術(shù)思維廣度和縱向探索深度。好啦，接下來(lái)小傅哥就給大家介紹幾種用于計(jì)算最小公倍數(shù)的算法。

五、用公約數(shù)實(shí)現(xiàn)

公式：lcm(a, b) = |a * b| / gcd(a, b)

public long lcm01(long m, long n){
    return ((m == 0) || (n == 0)) ? 0 : Math.abs(m * n) / gcd(m, n);
}

private long gcd(long m, long n){
    m = Math.abs(m);
    n = Math.abs(n);
    // 從一個(gè)數(shù)字中減去另一個(gè)數(shù)字，直到兩個(gè)數(shù)字變得相同。
    // 這將是 GCD。如果其中一個(gè)數(shù)字為零，也退出循環(huán)。
    // https://en.wikipedia.org/wiki/Euclidean_algorithm
    while (m != 0 && n != 0 && m != n) {
        if (m > n) {
            m = m - n;
        } else {
            n = n - m;
        }
    }
    return m == 0 ? n : m;
}

• 首先這里是一個(gè)比較簡(jiǎn)單的方式，基于兩數(shù)乘積除以最大公約數(shù)，得到的結(jié)果就是最小公倍數(shù)。

六、簡(jiǎn)單累加計(jì)算

此計(jì)算方式為，在一組正整數(shù)數(shù)列中，通過(guò)找到最小的數(shù)字進(jìn)行自身累加循環(huán)，直至所有數(shù)字相同時(shí)，則這個(gè)數(shù)字為最小公倍數(shù)。—— 你能代碼實(shí)現(xiàn)一下嗎？

public long lcm02(long... n) {
    long[] cache = n.clone();
    // 以所有數(shù)字都相等作為條件
    while (!isEquals(n)) {
        System.out.println(JSON.toJSONString(n));
        long min = n[0];
        int idx = 0;
        for (int i = 0; i < n.length; i++) {
            if (min > n[i]) {
                min = n[i];
                idx = i;
            }
        }
        n[idx] = cache[idx] + min;
    }
    return n[0];
}

• 在代碼實(shí)現(xiàn)中，首先要把n個(gè)整數(shù)數(shù)列進(jìn)行克隆保存。因?yàn)槊看蜗嗉拥亩际亲畛醯倪@個(gè)數(shù)列里的數(shù)字值。接下來(lái)就是以所有數(shù)字都相等作為條件循環(huán)判斷，不斷地的累加最小的數(shù)值即可。最終返回的就是最小公倍數(shù)。

七、表格推演計(jì)算

表格計(jì)算方式為將一組數(shù)字以最小的質(zhì)數(shù)2開(kāi)始整除，直到不能被2整除后，用下一個(gè)質(zhì)數(shù)3繼續(xù)整除（剩余的數(shù)字中比大的最小的質(zhì)數(shù)）直至所有數(shù)字都為1的時(shí)候結(jié)束。最終所有有效的質(zhì)數(shù)乘積就是最小公倍數(shù)?！?想想如果這讓你用代碼實(shí)現(xiàn)，你能肝出來(lái)嗎？

public long lcm03(long... n) {
    Map<Long, List<Long>> keys = new HashMap<>();
    for (long key : n) {
        keys.put(key, new ArrayList<Long>() {{
            add(key);
        }});
    }
    System.out.print("執(zhí)行表格計(jì)算：\r\nx ");
    long primality = 2, cachePrimality = primality, filterCount = 0, lcm = 1;
    // 以所有元素最后一位為1作為條件
    while (filterCount != keys.size()) {
        int refresh = 0;
        filterCount = 0;
        for (Map.Entry<Long, List<Long>> entry : keys.entrySet()) {
            long value = entry.getValue().get(entry.getValue().size() - 1);
            if (value == 1) {
                filterCount++;
            }
            // 整除處理
            if (value % primality == 0) {
                entry.getValue().add(value / primality);
                refresh++;
            } else {
                entry.getValue().add(value);
            }
        }
        // 刷新除數(shù)
        if (refresh == 0) {
            for (Map.Entry<Long, List<Long>> entry : keys.entrySet()) {
                long value = entry.getValue().get(entry.getValue().size() - 1);
                // 找到下一個(gè)符合的素?cái)?shù)
                if (value > primality || (value < cachePrimality && value > primality)) {
                    cachePrimality = value;
                }
                entry.getValue().remove(entry.getValue().size() - 1);
            }
            primality = cachePrimality;
        } else {
            // 累計(jì)乘積
            lcm *= cachePrimality;
            System.out.print(cachePrimality + " ");
        }
    }
    keys.forEach((key, values) -> {
        System.out.println();
        for (long v : values) {
            System.out.print(v + " ");
        }
    });
    System.out.println("\r\n");
    return lcm;
}

• 在代碼實(shí)現(xiàn)中我們通過(guò) Map 作為表的key，Map 中的 List 作為表每一行數(shù)據(jù)。通過(guò)這樣一個(gè)結(jié)構(gòu)構(gòu)建出一張表。
• 接下來(lái)以所有元素最后一位為1作為條件循環(huán)處理數(shù)據(jù)，用最開(kāi)始的2作為素?cái)?shù)整除列表中的數(shù)據(jù)，并保存到下一組數(shù)列中。當(dāng)2不能整除時(shí)，則刷新素?cái)?shù)，選取另外一個(gè)列表中最小的素?cái)?shù)作為除數(shù)繼續(xù)。
• 這個(gè)過(guò)程中會(huì)累計(jì)有效素?cái)?shù)的乘積，這個(gè)乘積的最終結(jié)果就是最小公倍數(shù)。

八、測(cè)試驗(yàn)證

單元測(cè)試

@Test
public void test_euclidean() {
    LastCommonMultiple lastCommonMultiple = new LastCommonMultiple();
    // System.out.println("最小公倍數(shù)：" + lastCommonMultiple.lcm01(2, 7));
    System.out.println("最小公倍數(shù)：" + lastCommonMultiple.lcm02(3, 4, 6));
    // System.out.println("最小公倍數(shù)：" + lastCommonMultiple.lcm03(3, 4, 6));
     System.out.println("最小公倍數(shù)：" + lastCommonMultiple.lcm03(3, 4, 6, 8));
   //System.out.println("最小公倍數(shù)：" + lastCommonMultiple.lcm03(4, 7, 12, 21, 42));
}

測(cè)試結(jié)果

執(zhí)行累加計(jì)算：
[3,4,6]
[6,4,6]
[6,8,6]
[9,8,6]
[9,8,12]
[9,12,12]
最小公倍數(shù)：12

執(zhí)行表格計(jì)算：
x 2 2 2 3 
3 3 3 3 1 
4 2 1 1 1 
6 3 3 3 1 
8 4 2 1 1 

最小公倍數(shù)：24

• 到這里測(cè)試就結(jié)束了，本章一共介紹了三種計(jì)算最小公倍數(shù)的方法。那如果只讓你看到邏輯，你能寫(xiě)出最終的代碼嗎？

九、常見(jiàn)面試

• 最大公約數(shù)的使用用途？
• 如何使用代碼實(shí)現(xiàn)最大公約數(shù)計(jì)算？
• 你是否了解歐幾里德算法？
• 關(guān)于數(shù)論你還記得多少？
• RSA 加密算法為什么需要用到公約數(shù)計(jì)算？
• 如何計(jì)算兩數(shù)的最小公倍數(shù)？
• 如果計(jì)算多個(gè)整數(shù)的最小公倍數(shù)？
• 你能說(shuō)一下具體如何實(shí)現(xiàn)這種X的計(jì)算流程嗎？
• 你知道最小公倍數(shù)計(jì)算的用途嗎？

• What is the most efficient way to calculate the least common multiple of two integers?：https://stackoverflow.com/questions/3154454/what-is-the-most-efficient-way-to-calculate-the-least-common-multiple-of-two-int/3154503#3154503
• Least common multiple：https://en.wikipedia.org/wiki/Least_common_multiple
• Chebyshev function：https://en.wikipedia.org/wiki/Chebyshev_function
• 歐幾里德算法：https://en.wikipedia.org/wiki/Euclidean_algorithm
• 線性組合：https://en.wikipedia.org/wiki/Linear_combination
• 貝祖定理：https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity?