Java第24题：求两个正整数的最小公倍数

题目

从标准输入读入两个正整数 a 和 b，计算并输出它们的最小公倍数（LCM）。

输入格式：一行输入两个正整数 a 和 b，以空格分隔。数据范围：1 ≤ a, b ≤ 10⁹。

输出格式：输出一个整数，表示 a 和 b 的最小公倍数，末尾输出换行。

思路与算法

1. 数学原理
两个正整数 a 和 b 的最大公约数记为 gcd(a, b)，最小公倍数记为 lcm(a, b)。由数论性质可知，两数之积等于它们最大公约数与最小公倍数的乘积，即：
a × b = gcd(a, b) × lcm(a, b)
由此推导最小公倍数的计算公式为：
lcm(a, b) = (a × b) / gcd(a, b)

2. 核心考点：运算顺序与防溢出
如果代码中直接计算 (a * b) / gcd，当两个数都在 10⁵ 左右时，乘积 a * b 会达到 10¹⁰，超出 32 位有符号整型 int 的上限（约 2.14×10⁹），导致溢出错误。
因为 gcd 是 a 的公因数，a / gcd 一定能整除。所以应当先除后乘：
(long)a / gcd * b
先除法后乘法既不会损失精度，又能有效控制计算的中间数值，避免溢出。同时使用 long 保存计算结果。

3. 辗转相除法求 GCD
求解最大公约数使用欧几里得算法（辗转相除法）：gcd(a, b) = gcd(b, a % b)，重复取余直到余数为 0，此时的除数就是最大公约数。单次计算的时间复杂度为 O(log(min(a, b)))。

完整程序

import java.util.Scanner;

public class Main {
    // 辗转相除法求两数最大公约数（欧几里得算法）
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();

        long g = gcd(a, b);
        // 核心考点：先除后乘防止 (a * b) 超出范围溢出
        long lcm = (a / g) * b;

        System.out.println(lcm);
    }
}

运行示例

示例 1（常规数值）：

输入：

4 6

输出：

12

示例 2（较大数值）：

输入：

150000 250000

输出：

750000