C語言經典習題：輾轉相除法求最大公約數與最小公倍數

題目描述

輸入兩正整數 m, n，求最大公約數 (GCD) 與最小公倍數 (LCM)。

算法：輾轉相除法

gcd(a, b):
    while b ≠ 0:
        t = a % b
        a = b
        b = t
    return a

lcm(a, b) = a * b / gcd(a, b)

完整代碼

#include 
#include 

int main() {
    int a, b, num1, num2, temp;
    printf("please input two numbers:\n");
    scanf("%d,%d", &num1, &num2);
    if (num1 < num2) { temp = num1; num1 = num2; num2 = temp; }
    a = num1; b = num2;
    while (b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    printf("gcd:%d\n", a);
    printf("lcm:%d\n", num1 * num2 / a);
    getch();
    return 0;
}

運行示例

輸入 12,18 → GCD=6, LCM=36