C++求最大公約數和最小公倍數的實現方法

一、背景介紹

在數學中，最大公約數（Greatest Common Divisor, 簡稱GCD）和最小公倍數（Least Common Multiple, 簡稱LCM）是兩個非常重要的概念。

最大公約數是指兩個或多個整數共有約數中最大的一個，例如 8 和 12 的最大公約數是 4。

最小公倍數是指兩個或多個整數公有的倍數中最小的一個，例如 4 和 6 的最小公倍數是 12。

獲得最大公約數和最小公倍數有很多方法，本文將介紹用C++實現的方法。

二、輾轉相除法

輾轉相除法，又稱歐幾里得演算法，是求最大公約數的經典方法。該演算法基於如下性質：兩個正整數a和b（a>b）的最大公約數等於a除以b的餘數c和b之間的最大公約數。

代碼實現如下：

int gcd(int a, int b)
{
    if (a < b)  //保證a大於b
        swap(a, b);
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

對於求最小公倍數，可以先使用輾轉相除法求出最大公約數，然後套用以下公式：

最小公倍數 = a×b / 最大公約數

代碼實現如下：

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

三、更相減損術

更相減損術是另一種求最大公約數的方法。該演算法基於如下性質：兩個正整數a和b（a>b）的最大公約數等於a-b的差值c和較小數b之間的最大公約數。

代碼實現如下：

int gcd(int a, int b)
{
    if (a < b)
        swap(a, b);
    while (a - b != b)  //循環終止條件為 a-b=b
    {
        int temp = a - b;
        a = max(b, temp);
        b = min(b, temp);
    }
    return b;
}

但是，這種演算法的效率遠低於輾轉相除法，因此不常用。

四、更優秀的實現

雖然輾轉相除法已經很優秀了，但是還是可以進一步優化。

一種優化的方法是 Stein演算法，結合了更相減損術和位移運算的思想。該演算法在計算機上運行的效率比輾轉相除法要高，因為位移運算比除法運算要快。

代碼實現如下：

int gcd(int a, int b)
{
    if (a == 0) return b;
    if (b == 0) return a;
    int shift;
    for (shift = 0; ((a | b) & 1) == 0; ++shift)
    {
        a >>= 1;
        b >>= 1;
    }
    while ((a & 1) == 0)  a >>= 1;
    do {
        while ((b & 1) == 0)  b >>= 1;
        if (a > b)  swap(a, b);
        b -= a;
    } while (b != 0);
    return a << shift;
}

對於求最小公倍數，也可以使用 Stein演算法。代碼實現如下：

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

五、總結

求最大公約數和最小公倍數是我們在編程中經常會碰到的問題，本文主要介紹了輾轉相除法、更相減損術和 Stein演算法三種方法，其中輾轉相除法是應用最廣泛的。

需要注意的是，在使用求最小公倍數公式時，由於乘法運算的結果可能超出 int 類型的範圍，因此需要使用更高精度的數據類型，如 long long。

希望本文能夠對讀者有所幫助。