Finding the Least Common Multiple in Java – 寻找Java中的最小公倍数

最后修改: 2019年 8月 20日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

The Least Common Multiple (LCM) of two non-zero integers (a, b) is the smallest positive integer that is perfectly divisible by both a and b.

两个非零整数的最小公倍数（LCM）（a，b）是完全可以被a和b整除的最小正整数。。

In this tutorial, we’ll learn about different approaches to find the LCM of two or more numbers. We must note that negative integers and zero aren’t candidates for LCM.

在本教程中，我们将学习寻找两个或多个数字的LCM的不同方法。我们必须注意，负整数和零不是LCM的候选数。

2. Calculating LCM of Two Numbers Using a Simple Algorithm

2.用一个简单的算法计算两个数字的LCM

We can find the LCM of two numbers by using the simple fact that multiplication is repeated addition.

我们可以通过以下简单的事实来找到两个数字的LCM：乘法是重复加法。

2.1. Algorithm

2.1.算法

The simple algorithm to find the LCM is an iterative approach that makes use of a few fundamental properties of LCM of two numbers.

寻找LCM的简单算法是一种迭代方法，利用了两个数字的LCM的一些基本属性。

Firstly, we know that the LCM of any number with zero is zero itself. So, we can make an early exit from the procedure whenever either of the given integers is 0.

首先，我们知道任何数字的0的LCM是0本身。因此，只要给定的任何一个整数是0，我们就可以提前退出这个程序。

Secondly, we can also make use of the fact that the lower bound of the LCM of two non-zero integers is the larger of the absolute values of the two numbers.

其次，我们还可以利用这样一个事实：两个非零整数的LCM的下限是这两个数字的绝对值中较大的一个。

Moreover, as explained earlier, the LCM can never be a negative integer. So, we’ll only use absolute values of the integers for finding the possible multiples until we find a common multiple.

此外，正如前面所解释的，LCM不可能是一个负整数。因此，我们将只使用整数的绝对值来寻找可能的倍数，直到我们找到一个公倍数。

Let’s see the exact procedure that we need to follow for determining lcm(a, b):

让我们看看确定lcm(a, b)需要遵循的确切程序。

  1. If a = 0 or b = 0, then return with lcm(a, b) = 0, else go to step 2.
  2. Calculate absolute values of the two numbers.
  3. Initialize lcm as the higher of the two values computed in step 2.
  4. If lcm is divisible by the lower absolute value, then return.
  5. Increment lcm by the higher absolute value among the two and go to step 4.

Before we start with the implementation of this simple approach, let’s do a dry-run to find lcm(12, 18).

在我们开始实施这个简单的方法之前，让我们先做个模拟，找到lcm（12，18）。

As both 12 and 18 are positive, let’s jump to step 3, initializing lcm = max(12, 18) = 18, and proceed further.

由于12和18都是正数，让我们跳到第3步，初始化lcm = max(12, 18) = 18，然后继续前进。

In our first iteration, lcm = 18, which isn’t perfectly divisible by 12. So, we increment it by 18 and continue.

在我们的第一次迭代中，lcm=18，这并不是完全可以被12整除的。因此，我们用18来增加它，然后继续。

In the second iteration, we can see that lcm = 36 and is now perfectly divisible by 12. So, we can return from the algorithm and conclude that lcm(12, 18) is 36.

在第二次迭代中，我们可以看到lcm=36，现在完全可以被12整除。因此，我们可以从算法中返回并得出结论：lcm(12, 18)是36。

2.2. Implementation 

2.2.实施

Let’s implement the algorithm in Java. Our lcm() method needs to accept two integer arguments and give their LCM as a return value.

让我们用Java来实现这个算法。我们的lcm()方法需要接受两个整数参数，并将其LCM作为返回值。

We can notice that the above algorithm involves performing a few mathematical operations on the numbers such as finding absolute, minimum, and maximum values. For this purpose, we can use the corresponding static methods of the Math class such as abs(), min(), and max(), respectively.

我们可以注意到，上述算法涉及对数字进行一些数学运算，如寻找绝对值、最小值和最大值。为此，我们可以使用Math类的相应静态方法，如abs()、min()和max()。

Let’s implement our lcm() method:

让我们来实现我们的lcm()方法。

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;
}

Next, let’s also validate this method:

接下来，让我们也验证一下这个方法。

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

The above test case verifies the correctness of the lcm() method by asserting that lcm(12, 18) is 36.

上述测试案例通过断言lcm(12, 18)是36，验证了lcm()方法的正确性。

3. Using the Prime Factorization Approach

3.使用质因数法的方法

The fundamental theorem of arithmetic states that it’s possible to uniquely express every integer greater than one as a product of powers of prime numbers.

算术基本定理指出，可以将每个大于1的整数唯一地表达为素数幂的乘积。。

So, for any integer N > 1, we have N = (2k1) * (3k2) * (5k3) *…

因此，对于任何整数N>1，我们有N=（2k1）*（3k2）*（5k3）*。

Using the result of this theorem, we’ll now understand the prime factorization approach to find the LCM of two numbers.

利用这个定理的结果，我们现在就来了解一下用质因数法来寻找两个数字的LCM。

3.1. Algorithm

3.1.算法

The prime factorization approach calculates the LCM from the prime decomposition of the two numbers. We can use the prime factors and exponents from the prime factorization to calculate LCM of the two numbers:

质因数分解法从两个数字的质因数分解中计算出LCM。我们可以利用质因数分解法中的质因数和指数来计算这两个数的LCM。

When, |a| = (2p1) * (3p2) * (5p3) * …
and |b| = (2q1) * (3q2) * (5q3) * …
then, lcm(a, b) = (2max(p1, q1)) * (3max(p2, q2)) * (5max(p3, q3)) …

当，|a|=（2p1）*（3p2）*（5p3）*…
和|b| = (2q1) * (3q2) * (5q3) * …
那么，lcm(a, b) = (2max(p1, q1)) * (3max(p2, q2)) * (5max(p3, q3) …

Let’s see how to calculate the LCM of 12 and 18 using this approach:

让我们看看如何用这种方法来计算12和18的LCM。

Firstly, we need to represent the absolute values of the two numbers as products of prime factors:
12 = 2 * 2 * 3 = 2² * 3¹
18 = 2 * 3 * 3 = 2¹ * 3²

首先，我们需要将两个数字的绝对值表示为质因数的乘积：
12 = 2 * 2 * 3 = 2² * 3¹
18 = 2 * 3 * 3 = 2¹ * 3²

We can notice here that the prime factors in the above representations are 2 and 3.

在这里我们可以注意到，上述表述中的质因数是2和3。

Next, let’s determine the exponent of each prime factor for the LCM. We do this by taking its higher power from the two representations.

接下来，让我们确定LCM的每个质因数的指数。我们通过从这两个表示法中取其高次幂来实现这一目标。

Using this strategy, the power of 2 in the LCM will be max(2, 1) = 2, and the power of 3 in the LCM will be max(1, 2) = 2.

使用这种策略，LCM中2的幂将是max(2, 1)=2，而LCM中3的幂将是max(1, 2)=2。

Finally, we can compute the LCM by multiplying the prime factors with a corresponding power obtained in the previous step. Consequently, we have lcm(12, 18) = 2² * 3² = 36.

最后，我们可以通过将质因数与上一步得到的相应幂相乘来计算LCM。因此，我们有lcm(12, 18) = 2² * 3² = 36。

3.2. Implementation

3.2.实施

Our Java implementation uses prime factorization representation of the two numbers to find the LCM.

我们的Java实现使用两个数字的质因数表示法来寻找LCM。

For this purpose, our getPrimeFactors() method needs to accept an integer argument and give us its prime factorization representation. In Java, we can represent prime factorization of a number using a HashMap where each key denotes the prime factor and the value associated with the key signifies the exponent of the corresponding factor.

为此，我们的getPrimeFactors()方法需要接受一个整数参数，并给我们提供其质因数表示。在Java中，我们可以使用HashMap来表示一个数字的质因数，其中每个键表示质因数，与键相关的值表示相应因子的指数。

Let’s see an iterative implementation of the getPrimeFactors() method:

让我们看看getPrimeFactors()方法的迭代实现。

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

    Map<Integer, Integer> primeFactorsMap = new HashMap<Integer, Integer>();

    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;
}

We know that the prime factorization maps of 12 and 18 are {2 → 2, 3 → 1} and {2 → 1, 3 → 2} respectively. Let’s use this to test the above method:

我们知道，12和18的质因数图分别为{2→2，3→1}和{2→1，3→2}。让我们用这个来检验上述方法。

@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));
}

Our lcm() method first uses the getPrimeFactors() method to find prime factorization map for each number. Next, it uses the prime factorization map of both the numbers to find their LCM. Let’s see an iterative implementation of this method:

我们的lcm()方法首先使用getPrimeFactors()方法来寻找每个数字的质因数图。接下来，它使用两个数字的质因数图来找到它们的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;
}

As a good practice, we shall now verify the logical correctness of the lcm() method:

作为一个良好的实践，我们现在将验证lcm()方法的逻辑正确性。

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

4. Using the Euclidean Algorithm

4.使用欧几里得算法

There’s an interesting relation between the LCM and GCD (Greatest Common Divisor) of two numbers that says that the absolute value of the product of two numbers is equal to the product of their GCD and LCM.

在两个数字的LCM和GCD（最大公除数）之间有一个有趣的关系，即两个数字的积的绝对值等于它们的GCD和LCM的乘积。

As stated, gcd(a, b) * lcm(a, b) = |a * b|.

如前所述，gcd(a, b) * lcm(a, b) = |a * b|。

Consequently, lcm(a, b) = |a * b|/gcd(a, b).

因此，lcm(a, b) = |a * b|/gcd(a, b)。

Using this formula, our original problem of finding lcm(a,b) has now been reduced to just finding gcd(a,b).

使用这个公式，我们原来寻找lcm(a,b)的问题现在已经减少到只寻找gcd(a,b)。

Granted, there are multiple strategies to finding GCD of two numbers. However, the Euclidean algorithm is known to be one of the most efficient of all.

诚然，寻找两个数字的GCD有多种策略。然而，欧几里得算法被认为是所有算法中效率最高的一种。

For this reason, let’s briefly understand the crux of this algorithm, which can be summed up in two relations:

出于这个原因，让我们简单了解一下这个算法的核心，它可以归纳为两个关系。

  • gcd (a, b) = gcd(|a%b|, |a| ); where |a| >= |b|
  • gcd(p, 0) = gcd(0, p) = |p|

Let’s see how we can find lcm(12, 18) using the above relations:

让我们看看如何利用上述关系找到lcm(12, 18)。

We have gcd(12, 18) = gcd(18%12, 12) = gcd(6,12) = gcd(12%6, 6) = gcd(0, 6) = 6

我们有gcd(12, 18) = gcd(18%12, 12) = gcd(6,12) = gcd(12%6, 6) = gcd(0, 6) = 6

Therefore, lcm(12, 18) = |12 x 18| / gcd(12, 18) = (12 x 18) / 6 = 36

因此，lcm(12, 18) = |12 x 18| / gcd(12, 18) = (12 x 18) / 6 = 36

We’ll now see a recursive implementation of the Euclidean algorithm:

我们现在将看到一个欧氏算法的递归实现。

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);
    }
}

The above implementation uses the absolute values of numbers — since GCD is the largest positive integer that perfectly divides the two numbers, we’re not interested in negative divisors.

上面的实现使用了数字的绝对值–因为GCD是完全除以两个数字的最大正整数，所以我们对负数除数不感兴趣。

We’re now ready to verify if the above implementation works as expected:

我们现在准备验证上述实现是否如预期那样工作。

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

4.1. LCM of Two Numbers

4.1.两个数字的最小值

Using the earlier method to find GCD, we can now easily calculate LCM. Again, our lcm() method needs to accept two integers as input to return their LCM. Let’s see how we can implement this method in Java:

使用先前的方法来寻找GCD，我们现在可以轻松地计算LCM。同样，我们的lcm()方法需要接受两个整数作为输入来返回它们的LCM。让我们看看如何在Java中实现这个方法。

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;
    }
}

We can now verify the functionality of the above method:

我们现在可以验证上述方法的功能。

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

4.2. LCM of Large Numbers Using the BigInteger Class

4.2.使用BigInteger类实现大数的LCM

To calculate the LCM of large numbers, we can leverage the BigInteger class.

为了计算大数的LCM，我们可以利用BigInteger类。

Internally, the gcd() method of the BigInteger class uses a hybrid algorithm to optimize computation performance. Moreover, since the BigInteger objects are immutable, the implementation leverages mutable instances of the MutableBigInteger class to avoid frequent memory reallocations.

在内部，BigInteger类的gcd()方法使用混合算法来优化计算性能。此外，由于BigInteger对象是不可变的，该实现利用了MutableBigInteger类的可变实例来避免频繁的内存重新分配。

To begin with, it uses the conventional Euclidean algorithm to repeatedly replace the higher integer by its modulus with the lower integer.

首先，它使用传统的欧几里得算法，用较低的整数反复替换较高的整数的模数。

As a result, the pair not only gets smaller and smaller but also closer to each other after successive divisions. Eventually, the difference in the number of ints required to hold the magnitude of the two MutableBigInteger objects in their respective int[] value arrays reaches either 1 or 0.

结果是，这对对象不仅越来越小，而且在连续除法后也越来越接近对方。最终，在两个MutableBigInteger对象各自的int[] 值数组中容纳其大小所需的int数量的差异达到了1或0。

At this stage, the strategy is switched to the Binary GCD algorithm to get even faster computation results.

在这个阶段，策略切换到二进制GCD算法以获得更快的计算结果。

In this case, as well, we’ll compute LCM by dividing the absolute value of the product of the numbers by their GCD. Similar to our prior examples, our lcm() method takes two BigInteger values as input and returns the LCM for the two numbers as a BigInteger. Let’s see it in action:

在这种情况下，我们也将通过用数字的乘积的绝对值除以其GCD来计算LCM。与之前的例子类似，我们的lcm()方法将两个BigInteger值作为输入，并将这两个数字的LCM作为BigInteger返回。让我们看看它的操作。

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

Finally, we can verify this with a test case:

最后，我们可以用一个测试案例来验证。

@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));
}

5. Conclusion

5.总结

In this tutorial, we discussed various methods to find the least common multiple of two numbers in Java.

在本教程中，我们讨论了在Java中寻找两个数字的最小公倍数的各种方法。

Moreover, we also learned about the relation between the product of numbers with their LCM and GCD. Given algorithms that can compute the GCD of two numbers efficiently, we’ve also reduced the problem of LCM calculation to one of GCD computation.

此外，我们还了解了数的乘积与它们的LCM和GCD之间的关系。考虑到可以有效地计算两个数字的GCD的算法，我们也将LCM的计算问题简化为GCD的计算问题。

As always, the complete source code for the Java implementation used in this article is available on GitHub.

一如既往，本文中使用的Java实现的完整源代码可在GitHub上获得。