Program to find the LCM of two numbers -2

This is Method 2 of finding the LCM of two given numbers and is a better way of finding the LCM compared to Method 1. It is better because, the number of times the for loop executes is reduced drastically. This benefit is explained in a detailed manner along with an example, at the end of this post.

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 Second Method of finding the L.C.M. of two numbers. Method 1 of finding the HCF can be read from here [Finding LCM – Method 1].

Solution:

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

import java.io.*;
class LcmMethod_2
{
public static void main()throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int a,b,max,min,x,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());
if(a>b)
{
max=a;
min=b;
}
else
{
max=b;
min=a;
}
/*
To find the maximum and minimum numbers, you can also use
int max=a>b?a:b;
int min=a<b?a:b;
*/
for(int i=1;i<=min;i++)
{
x=max*i; //finding multiples of the maximum number
if(x%min==0) //Finding the multiple of maximum number which is divisible by the minimum number.
{
lcm=x; //making the first multiple of maximum number which is divisible by the minimum number, as the LCM
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. 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 or equal to the maximum number. It cannot be less than it.

2. LCM of two numbers is a number which is a multiple of both the numbers.
For Example, if the 2 numbers are 336 and 224, then there LCM is 672 which is both a multiple of the maximum number (336 x 2 = 672) and also a multiple of the minimum number (224 x 3 = 672).
[Yes it is true. If you don’t believe me, then take any 2 numbers, find their LCM and check whether what I say is true or not.]

3. So since LCM is the multiple of both the maximum and the minimum number, then it won’t be wrong to use the following logic:

● Find multiples of the maximum number. [Since, LCM is either equal to or greater than the maximum number]
● Check whether this multiple is also a multiple of the minimum number or not, i.e. whether this multiple is divisible by the minimum number or not.
● If it is divisible, then this is our LCM and we have to stop, because though there may be many other such multiples, but we wanted to find the least multiple of both the numbers.

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

That is it. In this program, we have used the above logic only in order to find the LCM.

Benefit of using this method over [Method 1]:

The benefit is that the number of times the for loop is executing has been reduced a lot and hence our program becomes much more productive.

The benefit can be easily understood by taking an example:

If the two numbers are a = 336 and b = 224, then,

METHOD 1

METHOD 2

We used the following for loop: for(int i=a;i<=a*b;i++) { if(i%a==0 && i%b==0) { lcm=i; break; } } This for loop will start from 336 and is supposed to go until 336 x 224 = 75264 The LCM of the numbers 336 and 224 is 672. Since the loop first checks for 336, then 337, then 338 and so on till it gets a number which is divisible by both 336 and 224. In this case it is 672, hence after getting 672 the loop will stop, since it is the LCM. So the minimum number of times this for loop will execute is 336 times (672-336 = 336)

We used the following for loop: for(int i=1;i<=min;i++) { x=max*i; if(x%min==0) { lcm=x; break; }} The maximum number is 336, so this for loop will start from 336 and is supposed to go until 336 x 224 = 75264 This loop finds multiple of 336 i.e. first it calculates x=336×1=336, then 336×2=672 and so on. As soon as we get 672, the loop will stop, since it is a number which is divisible by 224 also, and hence is the LCM. We see here that we got the LCM in just 2 iteration of the loop, compared to 336 iterations of the 1st Method.

The greater the numbers are, the more number of times the for loop will execute. So this optimization in the LCM code, in order to reduce the number of times the for loop is executed, is really beneficial.