C++求最大公約數演算法實現

一、什麼是最大公約數

在數學中，最大公約數，簡稱為gcd，又稱最大公因數、最大公因子，指兩個或多個整數共有約數中最大的一個。

例如，12和16的最大公約數是4，一般表示為gcd(12, 16) = 4。

二、求最大公約數的幾種方法

目前求最大公約數的方法主要有以下幾種：

歐幾里得演算法

歐幾里得演算法，又稱輾轉相除法，是一種簡單卻又非常高效的求最大公約數的演算法。

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

該演算法的原理是，設a、b為兩個正整數，a>b，令r=a%b，將a替換為b，b替換為r，再計算a%b，直到r=0，則最大公約數為b。

更相減損術

更相減損術是另一種求最大公約數的演算法，其原理是，設a、b為兩個正整數，a>b，則a-b得到的差值可能是a的約數，也可能是b的約數。如果它是a、b的公約數，那麼直接返回這個差值即可；否則，將a、b的較小者替換為a-b，較大者替換為它們的差，繼續重複操作直到a或b為0。

int gcd(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
    return a;
}

質因數分解法

質因數分解法是另一種求最大公約數的方法。首先，將兩個數分別分解成質因數的乘積；然後，找出它們的所有公共質因數，將這些質因數相乘即為它們的最大公約數。

int gcd(int a, int b) {
    int r = 1;
    for (int i = 2; i <= min(a, b); i++) {
        if (a % i == 0 && b % i == 0) {
            r *= i;
            a /= i;
            b /= i;
            i = 1;
        }
    }
    return r;
}

三、各種方法的比較

由於歐幾里得演算法的效率最高，因此一般採用該演算法來求解最大公約數，而其他方法則很少使用。例如，對於1000與1001這兩個數，歐幾里得演算法只需要7次計算就可以求出它們的最大公約數，而質因數分解法需要對它們進行質因數分解，然後再進行比較，因此需要更多的計算次數。

四、總結

本文介紹了三種求最大公約數的演算法，它們分別是歐幾里得演算法、更相減損術和質因數分解法。其中，歐幾里得演算法效率最高，因此一般採用該演算法來求解最大公約數。

代碼示例

#include <iostream>
using namespace std;

// 求最大公約數 - 歐幾里得演算法
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main() {
    int a, b;
    cout << "請輸入兩個正整數：" <> a >> b;
    cout << a << "和" << b << "的最大公約數是：" << gcd(a, b) << endl;
    return 0;
}