Java Program to Find the LCM of Two Numbers
The LCM (Least Common Multiple) of two numbers is the smallest positive number that both of them divide into exactly. For example, the multiples of 4 are 4, 8, 12, 16, ... and the multiples of 6 are 6, 12, 18, ..., so LCM(4, 6) = 12.
The LCM and the GCD (greatest common divisor) are linked by a simple formula:
LCM(a, b) = a × b / GCD(a, b)
For 12 and 18: GCD = 6, so LCM = 12 × 18 / 6 = 36.
1. LCM by Checking Multiples
Start from the larger number and step through its multiples until one is also divisible by the smaller number.
public class LcmLoop {
public static void main(String[] args) {
int a = 12, b = 18;
int larger = Math.max(a, b);
int lcm = larger;
while (lcm % a != 0 || lcm % b != 0) {
lcm += larger;
}
System.out.println("LCM of " + a + " and " + b + " is " + lcm);
}
}LCM of 12 and 18 is 36
2. LCM Using the GCD Formula and User Input
The Euclidean algorithm finds the GCD quickly, and the formula turns it into the LCM. Dividing before multiplying (a / gcd * b) keeps the intermediate value small and avoids overflow.
import java.util.Scanner;
public class LcmUsingGcd {
static long gcd(long a, long b) {
while (b != 0) {
long r = a % b;
a = b;
b = r;
}
return a;
}
static long lcm(long a, long b) {
return a / gcd(a, b) * b;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the first number: ");
long a = scanner.nextLong();
System.out.print("Enter the second number: ");
long b = scanner.nextLong();
scanner.close();
System.out.println("GCD of " + a + " and " + b + " is " + gcd(a, b));
System.out.println("LCM of " + a + " and " + b + " is " + lcm(a, b));
}
}Enter the first number: 15 Enter the second number: 20 GCD of 15 and 20 is 5 LCM of 15 and 20 is 60
3. LCM of More Than Two Numbers
LCM(a, b, c) = LCM(LCM(a, b), c), so the LCM of a whole array can be built up one number at a time.
public class LcmArray {
static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
int[] numbers = {4, 6, 8, 10};
long lcm = numbers[0];
for (int i = 1; i < numbers.length; i++) {
lcm = lcm / gcd(lcm, numbers[i]) * numbers[i];
}
System.out.println("LCM of 4, 6, 8 and 10 is " + lcm);
}
}LCM of 4, 6, 8 and 10 is 120
4. Summary
- The LCM is the smallest number that both numbers divide into exactly.
- Stepping through multiples of the larger number works but can be slow.
LCM(a, b) = a / GCD(a, b) * bis fast and avoids overflow.- For several numbers, apply the LCM to the running result and the next number.