C語言練習實例16：最大公約數與最小公倍數（輾轉相除法）

輸入兩正整數，求最大公約數（GCD）和最小公倍數（LCM）。利用輾轉相除法（歐幾里得算法）求 GCD，LCM = a*b/GCD。

算法證明

設 c=gcd(a,b), a=kc, b=jc (k,j 互素)。r = a mod b = (k-mj)c，故 gcd(a,b)=gcd(b,r)。遞推直到余數為 0，當前除數即 GCD。

源代碼

// Created by www.runoob.com on 15/11/9.
// Copyright © 2015年 菜鳥教程. All rights reserved.
//
#include <stdio.h>

int main() {
    int a, b, t, r;
    printf("請輸入兩個數字：\n");
    scanf("%d %d", &a, &b);
    if (a < b) { t = b; b = a; a = t; }
    r = a % b;
    int n = a * b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    printf("這兩個數的最大公約數是%d，最小公倍數是%d\n", b, n / b);
    return 0;
}

運行示例

請輸入兩個數字：
12 26
這兩個數的最大公約數是2，最小公倍數是156

注意

a*b 可能溢出，大數時建議先除後乘：LCM = a / gcd * b。