Java 輾轉相除法求最大公約數與最小公倍數

GCD 與 LCM 數學與程式實作

最大公約數（GCD）與最小公倍數（LCM）是經典數論問題。本文說明輾轉相除法原理，並提供遞迴與迭代兩種 Java 實作。

數學關係

對任意正整數 a, b：a * b = GCD(a, b) * LCM(a, b)

遞迴版 GCD（輾轉相除法）

public static int gcdRecursive(int a, int b) {
    if (b == 0) return a;
    return gcdRecursive(b, a % b);
}

迭代版 GCD（避免堆疊溢位）

public static int gcdIterative(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

完整主程式

import java.util.Scanner;

public class GcdLcmDemo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("請輸入兩個正整數：");
        long a = sc.nextLong();
        long b = sc.nextLong();

        long gcd = gcdIterative(a, b);
        long lcm = a / gcd * b; // 先除後乘避免溢位
        System.out.println("最大公約數：" + gcd);
        System.out.println("最小公倍數：" + lcm);
    }

    // 迭代版 GCD 方法放這裡...
}

效能與注意事項

• 迭代版優於遞迴版，無堆疊溢位風險。
• LCM 計算用 a / gcd * b 而非 a * b / gcd，減少中間結果溢位機率。
• 輸入為 0 時需特殊處理（GCD(0, n) = n, LCM(0, n) = 0）。