In this post we'll see how to write a Java program to calculate LCM (Least Common Multiple) of two numbers.
The least common multiple (LCM) is the smallest positive integer that is a multiple of two or more given numbers (perfectly divisible by the numbers).
For example, LCM of 14 and 16 is-
14 = 2 X 7 16 = 2 X 2 X 2 X 2 LCM = 2 X 2 X 2 X 2 X 7 = 112
Java program to calculate LCM of two numbers can be written using following approaches-
- Brute force approach to find the common multiple
- Using prime factorization to find LCM
- Using GCD of two numbers to find LCM
1. LCM of two numbers using brute force approach - Java Program
In this iterative approach we go by the fact that the lower bound for the LCM of two positive integers is the greater of the two. For example, if numbers are 12 and 16 then the LCM won't be less than 16 at least.
If two numbers are and b then the logic is to divide the max of and b by both a and b until the number is completely divisible by both a and b. In each iteration keep incrementing max by 1.
while(true) {
if(max % num1 == 0 && max % num2==0) {
break;
}
max++;
}
Here is the complete Java program-
public class LCMProgram {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter first number: ");
int num1 = sc.nextInt();
System.out.println("Enter second number: ");
int num2 = sc.nextInt();
int lcm = calculateLCM(num1, num2);
System.out.println("LCM is " + lcm);
sc.close();
}
public static int calculateLCM(int num1, int num2) {
if(num1 == 0 || num2 == 0) {
return 0;
}
int max = num1 > num2 ? num1 : num2;
while(true) {
if(max % num1 == 0 && max % num2==0) {
break;
}
max++;
}
return max;
}
}
Output
Enter first number: 12 Enter second number: 16 LCM is 48 Enter first number: 0 Enter second number: 5 LCM is 0 Enter first number: 10 Enter second number: 30 LCM is 30
2. Using prime factorization to find LCM - Java Program
1. In this approach as first step find prime factors of each number. For example, if numbers are 14 and 16 then-
14 = 2 X 7 = 21 X 71 16 = 2 X 2 X 2 X 2 = 24
2.Identify the highest power of each prime factor. As per our example we have two distinct prime factors 2 and 7 with highest power as-
For 2 it is - 24 For 7 it is - 71
3. Multiply the highest powers of each prime factors together to get the LCM
24 X 71 = 16 X 7 = 112
Java program for this approach can be written using HashMap where key is the factor and value is its power. For two numbers we'll have two maps with these entries.
Then for each key find the max power among all the maps.
Here is the complete Java program.
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class LCMProgram {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter first number: ");
int num1 = sc.nextInt();
System.out.println("Enter second number: ");
int num2 = sc.nextInt();
int lcm = calculateLCM(num1, num2);
System.out.println("LCM is " + lcm);
sc.close();
}
public static int calculateLCM(int num1, int num2) {
if(num1 == 0 || num2 == 0) {
return 0;
}
Map<Integer, Integer> factorsNum1 = getPrimeFactors(num1);
Map<Integer, Integer> factorsNum2 = getPrimeFactors(num2);
Set<Integer> allFactors = new HashSet<>();
// add keys in a Hashset to get distinct factors
allFactors.addAll(factorsNum1.keySet());
allFactors.addAll(factorsNum2.keySet());
int lcm = 1;
for(int factor: allFactors) {
// Look for the highest power for each factor
lcm *= Math.pow(factor, Math.max(factorsNum1.getOrDefault(factor, 0), factorsNum2.getOrDefault(factor, 0)));
}
return lcm;
}
private static Map<Integer, Integer> getPrimeFactors(int number){
Map<Integer, Integer> factors = new HashMap<>();
for(int i = 2; i< number/2; i++) {
while(number%i == 0) {
factors.put(i, factors.getOrDefault(i, 0)+1);
number = number/i;
}
}
// if number is not yet completely divisible, then it's a prime factor itself
if(number >2) {
factors.put(number, factors.getOrDefault(number, 0)+1);
}
return factors;
}
}
Output
Enter first number: 15 Enter second number: 25 LCM is 75
3. Using GCD of two numbers to find LCM - Java Program
Relationship between the two numbers for which LCM is calculated and their GCD is that the product of two numbers is equal to the product of LCM and GCD of those numbers.
For example, if a and b are two positive integers then
a * b = LCM(a, b) * GCD(a,b)
That means-
LCM(a, b) = (a*b) / GCD(a, b)
Refer Greatest Common Divisor (GCD) of Two Numbers Java Program to see different approaches for finding GCD of two numbers.
Here is the Java program for this approach-
public class LCMProgram {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter first number: ");
int num1 = sc.nextInt();
System.out.println("Enter second number: ");
int num2 = sc.nextInt();
int lcm = calculateLCM(num1, num2);
System.out.println("LCM is " + lcm);
sc.close();
}
public static int calculateLCM(int num1, int num2) {
if(num1 == 0 || num2 == 0) {
return 0;
}
int gcd = gcdEuclidDivision(num1, num2);
int lcm = (num1*num2)/gcd;
return lcm;
}
public static int gcdEuclidDivision(int a, int b) {
int temp;
// Find the maximum of two numbers, which is assigned to a
if(a < b) {
temp = a;
a = b;
b = temp;
}
while(b != 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
}
Output
Enter first number: 15 Enter second number: 25 LCM is 75
That's all for this topic Least Common Multiple (LCM) of Two Numbers - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
