# C++ Program to find the LCM of two numbers

## LCM of two numbers

Here we will discuss how to find the LCM of two numbers in C++ programming language. LCM, or least common multiple in mathematics, of two numbers is the smallest positive integer that is divisible by both the numbers.

### We will learn

• Method 1: A linear way to calculate LCM
• Method 2: Modified interval Linear way
• Method 3: Simple usage of HCF calculation to determine LCM
• Method 4: Repeated subtraction to calculate HCF and determine LCM
• Method 5: Recursive repeated subtraction to calculate HCF and determine LCM
• Method 6: Modulo Recursive repeated subtraction to calculate HCF and determine LCM

### Method 1

#### Algorithm

For a input num1 and num2. This method uses two following observations –

• LCM of two numbers will at least be equal or greater than max(num1, num2)
• Largest possibility of LCM will be num1 * num2

When iterating in (i) We can linearly find an (i) that is divisible by both num1 & num2

### Method 1 : C++ Code

Run
```#include<iostream>
using namespace std;

int main()
{
int num1 = 12, num2 = 14, lcm;

// finding the larger number here
int max = (num1 > num2)? num1 : num2;

// LCM will atleast be >= max(num1, num2)
// Largest possibility of LCM will be num1*num2
for(int i = max ; i <= num1*num2 ; i++)
{
if(i % num1 == 0 && i % num2 == 0){
lcm = i;
break;
}
}

cout<<"LCM of "<<num1<<" and "<<num2<<" is "<<lcm;

return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)```

### Output

`LCM of 12 and 14 is 84`

### Method 2

#### Algorithm

For input num1 and num2. This method uses two following observations –

• Rather than linearly checking for LCM by doing i++. We can do i = i + max
• Starting with i = max (num1, num2)
• The next possibility of LCM will be ‘max’ interval apart

### Method 2 : C++ Code

Run
```#include<iostream>
using namespace std;

int main()
{
int num1 = 12, num2 = 14, lcm;

// finding the larger number here
int max = (num1 > num2)? num1 : num2;

// can do i++ here
// but, i = i + max is done as next possibility of LCM will be
// max interval apart
for(int i = max ; i <= num1*num2 ; i=i+max)
{
if(i % num1 == 0 && i % num2 == 0){
lcm = i;
break;
}
}

cout<<"LCM of "<<num1<<" and "<<num2<<" is "<<lcm;

return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)```

### Output

`LCM of 12 and 14 is 84`

### Method 3

#### Algorithm

• Initialize HCF = 1
• Run a loop in the iteration of (i) between [1, min(num1, num2)]
• Note down the highest number that divides both num1 & num2
• If i satisfies (num1 % i == 0 && num2 % i == 0) then new value of HCF is i
• Use lcm formula :- (num1*num2) / hcf
• Print the output

### Method 3 : C++ Code

Run
```#include<iostream>
using namespace std;

int main()
{
int num1 = 12, num2 = 14, lcm;

// calculating LCM here
for(int i = 1; i <= num1 || i <= num2; i++) {
if(num1%i == 0 && num2%i == 0 )
lcm = i;
}

// LCM formula
lcm = (num1*num2)/lcm;

cout<<"LCM of "<<num1<<" and "<<num2<<" is "<<lcm;

return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)```

### Output

`LCM of 12 and 14 is 84`

### Method 4

#### Algorithm

• Run a while loop until num1 is not equals to num2
• If num1>num2 then num1 = num1 – num2
• Else num2 = num2 – num1
• After the loop ends both num1 & num2 stores HCF
• Use LCM formula :- (num1*num2) / hcf
• Print Output

### Method 4 : C++ Code

Run
```#include<iostream>
using namespace std;

int getHCF(int num1, int num2){

// using repeated subtraction here
while (num1 != num2)
{
if (num1 > num2)
num1 -= num2;
else
num2 -= num1;
}

return num1;
}

int main()
{
int num1 = 12, num2 = 14;

int hcf = getHCF(num1, num2);

// LCM formula
int lcm = (num1*num2)/hcf;
cout<<"LCM of "<<num1<<" and "<<num2<<" is "<<lcm;

return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)```

### Output

`LCM of 12 and 14 is 84`

### Method 5

#### Algorithm

• Checked whether any of the input is 0 then return sum of both numbers
• If both input are equal return any of the two numbers
• If num1 is greater than the num2 then Recursively call findHCF(num1 – num2, num2)
• Else Recursively call findHCF(num1, num2-num1)

### Method 5 : C++ Code

Run
```#include<iostream>
using namespace std;

// Recursive function for repeated subtraction HCF calculation
int getHCF(int num1, int num2)
{
// Handles the case when one of the number is 0 (num1)
// Check alert above in explanation
if (num1 == 0)
return num2;

// Handles the case when one of the number is 0 (num2)
// Check alert above in explanation
if (num2 == 0)
return num1;

// base case
if (num1 == num2)
return num1;

// num1 is greater
if (num1 > num2)
return getHCF(num1 - num2, num2);

else
return getHCF(num1, num2 - num1);
}

int main()
{
int num1 = 12, num2 = 14;

int hcf = getHCF(num1, num2);

// LCM formula
int lcm = (num1*num2)/hcf;

cout<<"LCM of "<<num1<<" and "<<num2<<" is "<<lcm;

return 0;
}```

### Output

`LCM of 12 and 14 is 84`

### Method 6

#### Algorithm

This method uses recursion.

In Addition, we are using modulo operation to reduce the number of subtractions required and improve the time complexity

For this method, you need to know how to calculate HCF, check this post here

We use repeated Modulo Recursive subtraction (Euclidean Algorithm) to calculate the HCF.

### Method 6 : C++ Code

Run
```#include<iostream>
using namespace std;
// This method improves complexity of repeated substraction
// By efficient use of modulo operator in euclidean algorithm
int getHCF(int a, int b)
{
return b == 0 ? a : getHCF(b, a % b);
}

int main()
{
int num1 = 12, num2 = 14;

int hcf = getHCF(num1, num2);

// LCM formula
int lcm = (num1*num2)/hcf;

cout<<"LCM of "<<num1<<" and "<<num2<<" is "<<lcm;

return 0;
}
// Time Complexity: log(max(a,b))```

### Output

`LCM of 12 and 14 is 84`

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

### 2 comments on “C++ Program to find the LCM of two numbers”

• SNAWGG

#include
#include

int lcm(int passedNumber1 , int passedNumber2)
{
int currentValue=std::min(passedNumber1,passedNumber2);
int inceremennt=currentValue;
while(true)
{
if(( currentValue % passedNumber1 ) ==0 && ( currentValue % passedNumber2 ) ==0)
{
break;
}
currentValue+=inceremennt;
}
return currentValue;
}
int main()
{
std::cout<<lcm(12,44);

}

• Satya Prakash

#include
using namespace std;
void lcm(int a,int b)
{
int result;
int max = (a>b)?a:b;
while(1){
if(max%a == 0 && max%b == 0)
{
result = max;
break;
}
++max;
}
cout<>a>>b;
lcm(a,b);

}