C++ 實現最大公約數（GCD）與最小公倍數（LCM）計算：歐幾里得算法詳解

歐幾里得算法（輾轉相除法）

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a; // 最大公約數
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b; // 避免溢出先除後乘
}

完整程式

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b) { int r = a % b; a = b; b = r; }
    return a;
}

int main() {
    int x, y;
    cout << "請輸入兩個正整數: ";
    cin >> x >> y;
    if (x <= 0 || y <= 0) {
        cerr << "輸入必須為正整數" << endl;
        return 1;
    }
    cout << "最大公約數 (GCD): " << gcd(x, y) << endl;
    cout << "最小公倍數 (LCM): " << (long long)x / gcd(x, y) * y << endl;
    return 0;
}

複雜度分析

• 時間複雜度：O(log min(a,b))
• 空間複雜度：O(1)

擴展：遞歸寫法

int gcd_recursive(int a, int b) {
    return b == 0 ? a : gcd_recursive(b, a % b);
}