C 語言實現最大公約數與最小公倍數

C 語言實現最大公約數 (GCD) 與最小公倍數 (LCM)

數學原理

以 30 和 18 為例：
30 = 2 × 3 × 5
18 = 2 × 3 × 3

• 最大公約數 (GCD)：共同質因數乘積 = 2 × 3 = 6。
• 最小公倍數 (LCM)：包含兩數所有質因數，共同部分只算一次 = GCD × (30/GCD) × (18/GCD) = 6 × 5 × 3 = 90。
  通用公式：LCM(a, b) = a * b / GCD(a, b)。

若 GCD = 1（互質），則 LCM = a * b。

代碼實現（輾轉相除法 / 歐幾里得算法）

#include <stdio.h>

int main() {
    long n1, n2, total, temp;
    printf("請輸入兩個正整數: ");
    scanf("%ld %ld", &n1, &n2);

    total = n1 * n2;           // 保存乘積用於計算 LCM
    if (n1 < n2) { temp = n1; n1 = n2; n2 = temp; } // 確保 n1 >= n2

    // 歐幾里得算法求 GCD
    while ((n1 % n2) != 0) {
        temp = n1 % n2;
        n1 = n2;
        n2 = temp;
    }
    // 循環結束時 n2 即為 GCD
    printf("最大公約數 (GCD) = %ld\n", n2);
    printf("最小公倍數 (LCM) = %ld\n", total / n2);
    return 0;
}

運行示例

請輸入兩個正整數: 30 18
最大公約數 (GCD) = 6
最小公倍數 (LCM) = 90

擴展：由 GCD 和 LCM 反推原數

已知 GCD 和 LCM，LCM / GCD 為兩數「不同部分」乘積。將該乘積分解為兩因子（注意：相同質因數不可拆分到兩邊，否則改變 GCD），分別乘以 GCD 即得原數。
例：GCD=6, LCM=90，90/6=15=3×5。分解為 1×15 得 6, 90；分解為 3×5 得 18, 30。