Program to find the LCM of two numbers -1

Question:

Write a program in Java to find the Least Common Multiple (L.C.M.) of two numbers entered by the user.

Note: This is the first Method of finding the L.C.M. of two numbers. Method 2 of finding the HCF can be read from here [Finding LCM – Method 2].

Solution:

/*
[Finding the LCM of two numbers - Method 1]
[www.javaforschool.com]
*/

import java.io.*;
class LcmMethod_1
{
public static void main()throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int a,b,lcm=1;
System.out.print("Enter the 1st number : ");
a=Integer.parseInt(br.readLine());
System.out.print("Enter the 2nd number : ");
b=Integer.parseInt(br.readLine());
for(int i=a;i<=a*b;i++) //Even if you start the for loop by 1, you will get the answer, but starting it from either the first or the second number reduces the number of times the for loop is executed.
{
if(i%a==0 && i%b==0) //Checking the first number which is divisible by both the numbers
{
lcm=i;
break; //exiting from the loop, as we don't need anymore checking after getting the LCM
}
}
System.out.println("L.C.M. = "+lcm);
}
}

Output:

Enter the 1st number : 336
Enter the 2nd number : 224
L.C.M. = 672

Explanation:

In this program we are using the following logic:

1. We know that LCM of two numbers (in simple terms) is the least number which is divisible by both the numbers.

2. We also know that the LCM of two numbers can never be greater than the product of the two numbers.
Because, we have a formula which is : Product of two numbers = Their HCF * Their LCM
So, if we have two numbers, one saved in a variable ‘a’ and the other in variable ‘b’, then according to the formula, a*b=HCF*LCM.

3. Also, we know that if their is an LCM of two numbers, i.e. if they have any common multiple except 1, then it will always be greater than both the numbers or equal to the greater number. It cannot be less than any of the two numbers, more specifically, it cannot be less than the greater number among the two.

4. Also, if we dont have any common multiple, then the LCM is 1. That is why we have initialized the variable storing LCM as 1.

5. The for loop can either begin with 1 or the 1st number or the 2nd number. The only difference is in the number of times the for loop is executed.
● If it begins with 1, then the number of times the for loop executes will increase.
● If it begins with either the 1st or the 2nd number, then we will be following the logic mentioned in point 3 i.e. since we know that LCM cannot be less than any of the 2 numbers, why not start looking for LCM by starting the loop from any one of them. [Hmmm, lots of Mathematical logic being used, Right ?]
It will also reduce the number of times the for loop executes.

6. In the for loop, we are accessing all the numbers one by one starting from either the 1st or the 2nd number till the product of the 2 numbers, and checking whether these numbers are divisible by both the 1st as well as the 2nd number or not.

7. The moment we get a number which is divisible by both the 1st as well as the 2nd number, we save it as the LCM and exit from the loop, because we needed only the least number which is divisible by both numbers, and we got that, so we don’t need to check any further.

8. Finally, we are printing the LCM as the output.