Java 實作：輸入兩個正整數求最大公約數與最小公倍數

最大公約數（GCD）與最小公倍數（LCM）計算

在程式設計中，求兩個正整數的最大公約數（Greatest Common Divisor, GCD）與最小公倍數（Least Common Multiple, LCM）是經典的基礎練習。本文示範兩種常見演算法：遞迴實作輾轉相除法（歐幾里得演算法）與迴圈版本，並說明兩者關係：LCM(a, b) = a * b / GCD(a, b)。

方法一：遞迴實作輾轉相除法

public class CommonDivisor {
    public static void main(String[] args) {
        commonDivisor(24, 32); // 輸出：the biggest common divisor is :8
    }

    static int commonDivisor(int m, int n) {
        if (n < 0 || m < 0) {
            System.out.println("ERROR!");
            return -1;
        }
        if (n == 0) {
            System.out.println("the biggest common divisor is :" + m);
            return m;
        }
        return commonDivisor(n, m % n);
    }
}

遞迴版本程式碼簡潔，直接對應數學定義：gcd(m, n) = gcd(n, m mod n)，直到 n == 0 為止。

方法二：迴圈版本並同時求 LCM

import java.util.Scanner;

public class CandC {
    // 迴圈求最大公約數
    public static int gcd(int m, int n) {
        while (true) {
            if ((m = m % n) == 0) return n;
            if ((n = n % m) == 0) return m;
        }
    }

    public static void main(String[] args) throws Exception {
        int a = 23, b = 32; // 也可用 Scanner 讀取輸入
        int c = gcd(a, b);
        System.out.println("最小公倍數：" + a * b / c + "\n最大公約數：" + c);
    }
}

迴圈版本避免遞迴呼叫開銷，適合效能敏感場合。主程式示範如何利用 GCD 反推 LCM。

核心觀念總結

• 輾轉相除法時間複雜度 O(log min(m,n))，極高效。
• LCM 計算利用關係式 a * b = GCD(a,b) * LCM(a,b)。
• 實務上建議加入輸入驗證（正整數、非零）與長整型防溢位。