C++實現求兩個數的最大公約數

一、什麼是最大公約數

最大公約數（Greatest Common Divisor，簡稱GCD），也稱最大公因數，指兩個或多個整數共有約數中最大的一個。

在數學上，求解最大公約數是一類很基礎的問題。例如，對於數38和54，它們的最大公約數是2，表示38和54都可以被2整除。

二、算法思路

求兩個數的最大公約數有多種算法，這裡介紹兩種最為常見的算法：輾轉相除法和更相減損法。

三、輾轉相除法實現

輾轉相除法又稱歐幾里得算法，基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數相除餘數的最大公約數。

代碼實現如下：

int Gcd(int x, int y)
{
    return y == 0 ? x : Gcd(y, x % y);
}

四、更相減損法實現

更相減損法是另一種求解最大公約數的算法，它基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數相減的差的最大公約數。

代碼實現如下：

 
int Gcd(int x, int y)
{
    if (x == 0 || y == 0) return x + y;
    while (x != y)
    {
        if (x > y) x -= y;
        else y -= x;
    }
    return x;
}

五、代碼示例

下面給出完整的實現代碼：

#include <iostream>
using namespace std;

int Gcd(int x, int y)
{
    return y == 0 ? x : Gcd(y, x % y);
}

int Gcd2(int x, int y)
{
    if (x == 0 || y == 0) return x + y;
    while (x != y)
    {
        if (x > y) x -= y;
        else y -= x;
    }
    return x;
}

int main()
{
    int x = 38, y = 54;
    cout << "Gcd(" << x << ", " << y << ") = " << Gcd(x, y) << endl;
    cout << "Gcd2(" << x << ", " << y << ") = " << Gcd2(x, y) << endl;
    return 0;
}

六、總結

本文介紹了求解兩個數的最大公約數的兩種算法：輾轉相除法和更相減損法，並給出了C++代碼實現。

在實際應用中，輾轉相除法通常具有更高的效率，而更相減損法相對更容易理解。