Java中求最小公倍数的几种方法

1. 概述

最小公倍数（Least Common Multiple, LCM） 是指两个非零整数 a 和 b 的最小正整数，能同时被 a 和 b 整除。

本文将介绍在 Java 中计算两个或多个数的最小公倍数的几种实现方式。需要强调的是：✅ 负数和零不能参与 LCM 计算，它们没有数学意义上的最小公倍数。

2. 使用简单算法求两个数的 LCM

我们可以利用“乘法是重复加法”这一基本性质，通过迭代方式实现 LCM 计算。

2.1 算法思路

该方法是一种直观的迭代策略，依赖于 LCM 的几个基本性质：

若任意一个数为 0，则 LCM 为 0 ✅
两个非零整数的 LCM 至少不小于它们绝对值中的较大者（即下界）
LCM 必为正数，因此我们只处理绝对值

具体步骤如下：

若 a == 0 或 b == 0，直接返回 0
取两个数的绝对值
初始化 lcm = max(|a|, |b|)
若 lcm % min(|a|, |b|) == 0，则找到结果，返回 lcm
否则，lcm += max(|a|, |b|)，跳回第 4 步

以 lcm(12, 18) 为例走一遍：

初始：lcm = max(12,18) = 18
第一次：18 % 12 != 0 → lcm = 18 + 18 = 36
第二次：36 % 12 == 0 → 返回 36

结果正确。

2.2 Java 实现

public static int lcm(int number1, int number2) {
    if (number1 == 0 || number2 == 0) {
        return 0;
    }
    int absNumber1 = Math.abs(number1);
    int absNumber2 = Math.abs(number2);
    int absHigherNumber = Math.max(absNumber1, absNumber2);
    int absLowerNumber = Math.min(absNumber1, absNumber2);
    int lcm = absHigherNumber;
    while (lcm % absLowerNumber != 0) {
        lcm += absHigherNumber;
    }
    return lcm;
}

测试验证：

@Test
public void testLCM() {
    Assert.assertEquals(36, lcm(12, 18));
}

⚠️ 虽然逻辑简单，但该方法在数值较大时效率较低，属于“简单粗暴”型方案，适合教学理解，不推荐生产使用。

3. 使用质因数分解法

根据算术基本定理，任意大于 1 的整数都可以唯一表示为质数幂的乘积。

利用这一点，我们可以通过质因数分解来求 LCM。

3.1 算法原理

设：

|a| = 2^p1 × 3^p2 × 5^p3 × ...
|b| = 2^q1 × 3^q2 × 5^q3 × ...

则：

lcm(a, b) = 2^max(p1,q1) × 3^max(p2,q2) × 5^max(p3,q3) × ...

以 lcm(12, 18) 为例：

12 = 2² × 3¹
18 = 2¹ × 3²
取各质因数的最高次幂：2^max(2,1) × 3^max(1,2) = 2² × 3² = 4 × 9 = 36

结果正确。

3.2 Java 实现

我们用 HashMap<Integer, Integer> 表示质因数分解，键为质因数，值为指数。

public static Map<Integer, Integer> getPrimeFactors(int number) {
    int absNumber = Math.abs(number);
    Map<Integer, Integer> primeFactorsMap = new HashMap<>();

    for (int factor = 2; factor <= absNumber; factor++) {
        while (absNumber % factor == 0) {
            Integer power = primeFactorsMap.get(factor);
            if (power == null) {
                power = 0;
            }
            primeFactorsMap.put(factor, power + 1);
            absNumber /= factor;
        }
    }
    return primeFactorsMap;
}

测试验证：

@Test
public void testGetPrimeFactors() {
    Map<Integer, Integer> expectedPrimeFactorsMapForTwelve = new HashMap<>();
    expectedPrimeFactorsMapForTwelve.put(2, 2);
    expectedPrimeFactorsMapForTwelve.put(3, 1);

    Assert.assertEquals(expectedPrimeFactorsMapForTwelve, 
      PrimeFactorizationAlgorithm.getPrimeFactors(12));

    Map<Integer, Integer> expectedPrimeFactorsMapForEighteen = new HashMap<>();
    expectedPrimeFactorsMapForEighteen.put(2, 1);
    expectedPrimeFactorsMapForEighteen.put(3, 2);

    Assert.assertEquals(expectedPrimeFactorsMapForEighteen, 
      PrimeFactorizationAlgorithm.getPrimeFactors(18));
}

主方法 lcm() 利用两个数的质因数 map 求 LCM：

public static int lcm(int number1, int number2) {
    if(number1 == 0 || number2 == 0) {
        return 0;
    }

    Map<Integer, Integer> primeFactorsForNum1 = getPrimeFactors(number1);
    Map<Integer, Integer> primeFactorsForNum2 = getPrimeFactors(number2);

    Set<Integer> primeFactorsUnionSet = new HashSet<>(primeFactorsForNum1.keySet());
    primeFactorsUnionSet.addAll(primeFactorsForNum2.keySet());

    int lcm = 1;

    for (Integer primeFactor : primeFactorsUnionSet) {
        lcm *= Math.pow(primeFactor, 
          Math.max(primeFactorsForNum1.getOrDefault(primeFactor, 0),
            primeFactorsForNum2.getOrDefault(primeFactor, 0)));
    }

    return lcm;
}

测试：

@Test
public void testLCM() {
    Assert.assertEquals(36, PrimeFactorizationAlgorithm.lcm(12, 18));
}

✅ 优点：数学清晰，适合理解原理
❌ 缺点：实现复杂，性能一般，还需处理浮点转整（Math.pow 返回 double）

4. 使用欧几里得算法（推荐）

这是最高效的方法，基于一个关键数学关系：

gcd(a, b) × lcm(a, b) = |a × b|

因此：

lcm(a, b) = |a × b| / gcd(a, b)

问题就转化为求 gcd(a, b)，而欧几里得算法是求 GCD 的最优解之一。

欧几里得算法核心

gcd(a, b) = gcd(b, a % b)，其中 a >= b
gcd(a, 0) = a

递归实现：

public static int gcd(int number1, int number2) {
    if (number1 == 0 || number2 == 0) {
        return number1 + number2;
    } else {
        int absNumber1 = Math.abs(number1);
        int absNumber2 = Math.abs(number2);
        int biggerValue = Math.max(absNumber1, absNumber2);
        int smallerValue = Math.min(absNumber1, absNumber2);
        return gcd(biggerValue % smallerValue, smallerValue);
    }
}

测试：

@Test
public void testGCD() {
    Assert.assertEquals(6, EuclideanAlgorithm.gcd(12, 18));
}

4.1 两个数的 LCM 实现

public static int lcm(int number1, int number2) {
    if (number1 == 0 || number2 == 0)
        return 0;
    else {
        int gcd = gcd(number1, number2);
        return Math.abs(number1 * number2) / gcd;
    }
}

测试：

@Test
public void testLCM() {
    Assert.assertEquals(36, EuclideanAlgorithm.lcm(12, 18));
}

✅ 强烈推荐此方法：代码简洁、性能高、数学正确性有保障。

4.2 使用 BigInteger 处理大数

对于超出 int 范围的大数，Java 提供了 BigInteger 类，其 gcd() 方法内部采用混合算法（欧几里得 + 二进制 GCD）优化性能。

关键点：

BigInteger 是不可变对象
内部使用 MutableBigInteger 减少内存分配开销
小数阶段用欧几里得，接近时切换为更高效的二进制 GCD 算法

实现如下：

public static BigInteger lcm(BigInteger number1, BigInteger number2) {
    BigInteger gcd = number1.gcd(number2);
    BigInteger absProduct = number1.multiply(number2).abs();
    return absProduct.divide(gcd);
}

测试：

@Test
public void testLCM() {
    BigInteger number1 = new BigInteger("12");
    BigInteger number2 = new BigInteger("18");
    BigInteger expectedLCM = new BigInteger("36");
    Assert.assertEquals(expectedLCM, BigIntegerLCM.lcm(number1, number2));
}

⚠️ 注意：multiply() 和 divide() 是 BigInteger 的实例方法，别和基本类型搞混。

5. 总结

本文介绍了三种求 LCM 的方法：

方法	优点	缺点	推荐场景
简单迭代	易懂	效率低	学习理解
质因数分解	数学清晰	实现复杂	算法教学
欧几里得法	高效、简洁	需理解 GCD	✅ 生产环境首选

📌 核心结论：
LCM 问题可转化为 GCD 问题，而 gcd(a,b) * lcm(a,b) = |a*b| 是关键桥梁。

对于普通整数，使用 int + 欧几里得递归；
对于大数，直接上 BigInteger，调用其内置 gcd() 方法，简单粗暴又高效。

所有示例代码已托管至 GitHub：https://github.com/yourname/java-lcm-examples

Persistence

REST

Security