求兩個正整數的最大公約數與最小公倍數（輾轉相除法）

算法原理

最大公約數 (GCD)：輾轉相除法（歐幾里得算法），gcd(a,b) = gcd(b, a%b)，直到餘數為 0。

最小公倍數 (LCM)：利用公式 lcm(a,b) = a * b / gcd(a,b)。

C 實現

#include 

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

int main() {
    int m, n;
    printf("輸入兩個正整數: ");
    scanf("%d %d", &m, &n);

    int g = gcd(m, n);
    long long l = (long long)m * n / g; // 防溢出用 long long

    printf("最大公約數 GCD = %d\n", g);
    printf("最小公倍數 LCM = %lld\n", l);
    return 0;
}

遞歸版 GCD

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

複雜度分析

時間複雜度 O(log min(a,b))，極高效。輾轉相除法是數論基石，廣泛用於密碼學、分數運算等。