C 語言輾轉相除法求最大公約數與最小公倍數

算法原理

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

完整代碼

#include <stdio.h>

int main() {
    int num1, num2, a, b, temp;
    printf("請輸入兩個正整數: ");
    scanf("%d %d", &num1, &num2);

    // 確保 a >= b
    a = num1 > num2 ? num1 : num2;
    b = num1 > num2 ? num2 : num1;

    // 輾轉相除法求 GCD
    while (b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    int gcd = a;
    int lcm = num1 * num2 / gcd;

    printf("最大公約數: %d\n", gcd);
    printf("最小公倍數: %d\n", lcm);
    return 0;
}

關鍵點

• 輸入校驗：確保為正整數。
• 避免溢出：num1 * num2 可能超出 int 範圍，實際項目建議用 long long 或先除後乘。
• 標準庫替代：C++17 可用 std::gcd、std::lcm（<numeric>）。