Compute LCM of Two Numbers

“Compute LCM of Two Numbers” is a basic and important programming exercise problem, Here, we are given two numbers, entered by user and our task is to compute LCM (Lowest Common Multiple) of two numbers.

LCM: An LCM of two integers is a smallest possible integer which is divisible by both the numbers.

Example: 

INPUT: 
N1 = 72, N2 = 120
OUTPUT:
360

There are two possible ways to compute the LCM of two numbers.

1. Brute-Force, Using loops.
2. Using Formula, with GCD.

METHOD 1: Brute-Force

The steps required to find the LCM of two Numbers are as follows:

1. Scan the Numbers from user.
2. Find the maximum of two number and store it into ‘max’ variable.
3. Iterate a loop starting from max until an integer is found which is divisible by both the integers.
4. That integer will be the LCM.

C++ Program to compute the LCM of two numbers is as follows: 

#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    //Scan the number  
    int n1,n2;  
    cout<<"Enter the numbers:";  
    cin>>n1>>n2;  
      
    // Computing the LCM  
      
    int max = (n1 > n2) ? n1 : n2;  
    int LCM;  
    while(1)  
    {  
       if(max % n1 == 0 && max % n2 ==0)  
       {  
           LCM = max;  
           break;  
       }  
       max++;  
    }  
      
    // Printing the LCM  
    cout<<"The LCM of "<<n1<<" and "<<n2<<" is "<<LCM;  
}  

OUTPUT:
Enter the numbers: 72 120
The LCM of 72 and120 is 360

METHOD 2: Using GCD

We have seen in this post: How to find GCD. The LCM and GCD are interrelated, so we can find the LCM of two numbers using GCD of given numbers, as:

LCM = (n1 * n2) / GCD

C++ Program to compute the LCM of two numbers: 

#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    //Scan the number  
    int n1,n2;  
    cout<<"Enter the numbers:";  
    cin>>n1>>n2;  
      
    // Computing the GCD and then LCM  
    int GCD = 1;  
    for (int i = 1; i <= n1 && i <= n2; ++i)   
    {  
        if (n1 % i == 0 && n2 % i == 0)  
            GCD = i;  
    }  
    int LCM = (n1 * n2) / GCD;  
      
    // Printing the LCM  
    cout<<"The LCM of "<<n1<<" and "<<n2<<" is "<<LCM;  
}  

OUTPUT:
Enter the numbers: 72 120
The LCM of 72 and120 is 360