C語言求最大公約數與最小公倍數：輾轉相除法遞歸與非遞歸實現

C語言求最大公約數與最小公倍數：輾轉相除法遞歸與非遞歸實現

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

int gcd(int a, int b) {
    if (a < b) { int t=a; a=b; b=t; }
    while (b != 0) {
        int r = a % b;
        a = b; b = r;
    }
    return a;
}

遞歸版：return b==0 ? a : gcd(b, a%b);（需保證 a>=b 或內部交換）。

最小公倍數

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

完整測試程序

#include <stdio.h>
int main() {
    printf("GCD(15,9)=%d\n", gcd(15,9));   // 3
    printf("LCM(15,9)=%d\n", lcm(15,9));   // 45
    return 0;
}