LCM of two Numbers in Java

Introduction

The Least Common Multiple (LCM) of two or more numbers is the smallest positive number that can be divided by the numbers without leaving a remainder. LCM is also known by the terms: Lowest Common Multiple (LCM), Least Common Denominator, and Smallest Common Multiple. LCM (a, b) or lcm (a, b) are the symbols for it, where a and b are two numbers.

For example: LCM of $4$, $5$ and $6$ is $60$. Since $60$ is the smallest integer that is completely divisible by all three numbers.

Properties of LCM

LCM is associative, commutative and distributive, which means:

• Associative: LCM (a, b) = LCM (b, a)
• Commutative: LCM (a, b, c) = LCM (LCM (a, b), c) = LCM (a, LCM (b, c))
• Distributive: LCM (ka, kb, kc) = kLCM (a, b, c)

Now, that we know about LCM and its properties, let's now look at the different ways to find the LCM of two numbers.

LCM Using Prime Factorization Method

Our first approach involves finding the prime factors of each number and then calculating the LCM using those, the same way we used to do it in our earlier days at school. Below is the recursive code for the method:

Output:

LCM Using While loop and if Statement

The next method is by using the while loop and if statement. The method is pretty straightforward. Let's dive into the code and understand how it works:

Output:

In the above code, we have initialized the LCM to the greater number and kept incrementing it, until a number is found which is divisible by both numbers.

LCM Using Multiples of Numbers

The method of finding LCM using multiples of numbers is probably the least used approach. This is mainly because the method is very lengthy. This approach is carried out in two steps:

1. List each number's multiples until the first common multiple is discovered.
2. Choose the smallest multiple that all of the numbers have in common.

That's about it. Now, let's code it out:

Output:

Calculate LCM using GCD

Before discussing the method of calculating LCM using GCD, we should understand what GCD is: Greatest Common Divisor: It's the largest number that splits two or more numbers fully. It's also known as the Highest Common Factor (HCF) or the Greatest Common Factor (GCF).

There is also a relationship between GCD and LCM:

Using the above relation, we can easily find the LCM using the GCD. We can now look at the code for the same:

Output: