Java Program to Find LCM of two Numbers
What is LCM of Numbers ?
The smallest positive integer that is a multiple of two or more numbers is known as the LCM (Least Common Multiple). We can use prime factorization to find the LCM by taking the product of the highest powers of each prime factor, or we can list the multiples of each number and find the lowest one that appears in all the lists.
Steps to Find the Largest Among Three Numbers :
- Each integer should be divided into its prime elements.
- List every distinct prime factor that appears in every number.
- Choose the highest power that appears across all the numbers for each distinct prime factor.
- Multiply all the prime factors together, using the highest power for each factor.
Example to determine the LCM of 6 and 8 :
- Divide 6 into its prime elements to find: 6 = 2 * 3
- Factor 8 into its main components: 8 = 2 * 2 * 2
- Find the distinct prime factors: 2 and 3.
- Take into account the maximum power for 2 in either of the factorizations: 2^3 = 8.
- Choose the highest power that occurs for 3, then: 3^1 = 3.
- Add the prime elements together to get: LCM(6, 8) = 2^3 * 3^1 = 24.
So the LCM of 6 and 8 is 24.
Pseudo Code using while loop :
function LCM(a, b):
lcm = max(a, b)
while True:
if lcm % a == 0 and lcm % b == 0:
return lcm
lcm += max(a, b)
Example 1 :
Run
public class Main {
public static void main(String[] args) {
int a = 24, b = 36;
int lcm = findLCM(a, b);
System.out.println("LCM of " + a + " and " + b + " is " + lcm);
}
public static int findLCM(int a, int b) {
int lcm = Math.max(a, b);
while (true) {
if (lcm % a == 0 && lcm % b == 0) {
return lcm;
}
lcm += Math.max(a, b);
}
}
}
Output :
LCM of 24 and 36 is 72
Explanation :
Using a while loop, the findLCM() method uses two integer parameters, a and b, to return their LCM. In order to determine whether lcm is divisible by both a and b, it first initialises it to the largest value possible for a and b. If it is, the LCM is returned as lcm. If not, it increases lcm by the maximum of a and b and then repeats the loop.
Example 2 :
Run
public class Main {
public static void main(String[] args) {
int a = 24, b = 36;
int gcd = findGCD(a, b);
int lcm = (a * b) / gcd;
System.out.println("LCM of " + a + " and " + b + " is " + lcm);
}
public static int findGCD(int a, int b) {
if (b == 0) {
return a;
}
return findGCD(b, a % b);
}
}
Output :
LCM of 24 and 36 is 72
Explanation :
The main() method of the LCM class in this piece of Java code sets the initial values of two integer variables, a and b, to 24 and 36, respectively. Then, to calculate their GCD, it invokes the findGCD() function with the inputs a and b. The LCM is then calculated using the equation lcm = (a * b) / gcd. The outcome is then printed.
The findGCD() method uses the Euclidean technique to return the GCD of two integer arguments, a and b. It repeatedly invokes itself with the parameters b and a% b up until b is equal to 0, at which time it returns an as the GCD.
The findGCD() method uses the Euclidean technique to return the GCD of two integer arguments, a and b. It repeatedly invokes itself with the parameters b and a% b up until b is equal to 0, at which time it returns an as the GCD.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment