1. Overview
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.
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.
2. Calculating LCM of Two Numbers Using a Simple Algorithm
We can find the LCM of two numbers by using the simple fact that multiplication is repeated addition.
2.1. Algorithm
The simple algorithm to find the LCM is an iterative approach that makes use of a few fundamental properties of LCM of two numbers.
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.
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.
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.
Let’s see the exact procedure that we need to follow for determining lcm(a, b):
- If a = 0 or b = 0, then return with lcm(a, b) = 0, else go to step 2.
- Calculate absolute values of the two numbers.
- Initialize lcm as the higher of the two values computed in step 2.
- If lcm is divisible by the lower absolute value, then return.
- 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).
As both 12 and 18 are positive, let’s jump to step 3, initializing lcm = max(12, 18) = 18, and proceed further.
In our first iteration, lcm = 18, which isn’t perfectly divisible by 12. So, we increment it by 18 and continue.
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.
2.2. Implementation
Let’s implement the algorithm in Java. Our lcm() method needs to accept two integer arguments and give their LCM as a return value.
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.
Let’s implement our lcm() method:
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.
3. Using the Prime Factorization Approach
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.
So, for any integer N > 1, we have 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.
3.1. Algorithm
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:
When, |a| = (2p1) * (3p2) * (5p3) * …
and |b| = (2q1) * (3q2) * (5q3) * …
then, 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:
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²
We can notice here that the prime factors in the above representations are 2 and 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.
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.
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.
3.2. Implementation
Our Java implementation uses prime factorization representation of the two numbers to find the 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.
Let’s see an iterative implementation of the getPrimeFactors() method:
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:
@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:
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:
@Test
public void testLCM() {
Assert.assertEquals(36, PrimeFactorizationAlgorithm.lcm(12, 18));
}
4. Using the Euclidean Algorithm
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.
As stated, gcd(a, b) * lcm(a, b) = |a * b|.
Consequently, 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).
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.
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:
We have 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
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.
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
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:
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
To calculate the LCM of large numbers, we can leverage the BigInteger class.
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.
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.
At this stage, the strategy is switched to the Binary GCD algorithm to get even faster computation results.
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:
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
In this tutorial, we discussed various methods to find the least common multiple of two numbers in 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.
As always, the complete source code for the Java implementation used in this article is available on GitHub.