  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# C++ Program to Find the LCM of Two Numbers

Last Updated on May 5, 2023 by Prepbytes The lowest number which is a multiple of all the supplied numbers is known as the Least Common Multiple or LCM, of a collection of integers in mathematics. In C++, there are a variety of techniques you may use to get the LCM of two numbers, including the "if condition," "while loop," and GCD method, among others.

## What is the LCM of Two Numbers in C++?

The LCM, or least common multiple, is a method for determining the smaller of two numbers (n1 and n2) that may be divided by the given numbers. A number that is included in both numbers is known as a common multiple. The LCM of two integers is shown as LCM (a, b) or lcm (a, b).

### Algorithm of the LCM of Two Numbers

• Step 1: Take two inputs from the user n1 and n2
• Step 2: Store the smallest common multiple of n1 and n2 into the max variable.
• Step 3: Validate whether the max variable is divisible by n1 and n2, and print the max as the LCM of two numbers.
• Step 4: Otherwise, the max value is updated by 1 on every iteration, and jump to step 3 to check the divisibility of the max variable.
• Step 5: Terminate the program

## Methods to Find LCM of Two Numbers in C++

Below are discussed some methods to find LCM of two numbers in C++:

### Method 1 to Find LCM of Two Numbers Using if Statement

By taking the first lowest number that is divisible by both a and b, we may get the LCM of two numbers a and b. Using the if condition, we may initialize the max_num variable with maximum(a, b), then increase max_num by 1 until max_num is divisible by both a and b.

Code Implementation:

```#include <bits/stdc++.h>
using namespace std;

int main()
{
int a, b, max_num;
a=42;
b=63;
max_num= max(a,b);
while (1)
{
if(max_num % a == 0 && max_num % b == 0)
{
cout << " The LCM of " <<a << " and " << b << " is " << max_num << endl;
break;
}
++max_num;
}

return 0;
}
```

Output:

``The LCM of 42 and 63 is 126``

Time Complexity:
O(ab) as the while loop will run till it reaches the least common multiple of a and b. For example, 13 and 7 are the prime numbers whose LCM is 91. Here the loop starts from max(13,7)= 13 and ends at 91. Hence, the time complexity is found to be O(ab).

Space Complexity:
O(1) extra space is required as we are using int to save the previously calculated result.

### Method 2 to Find LCM of Two Numbers using GCD (While Loop)

In mathematics, we are aware that the sum of the products of the two integers a and b themselves is equal to their Least Common Multiple (LCM) and Greatest Common Divisor (GCD).

LCM(a,b)∗GCD(a,b)=a∗b

Deducing the above statement:

‘LCM(a,b)=a∗b/GCD(a,b)‘

By using a while loop to calculate GCD(a, b) and dividing the sum of a and b by GCD(a, b), we may determine the LCM of two integers, a and b. The Euclidean algorithm may be used to compute the GCD(a, b) by subtracting the smaller number from the bigger one between a and b until both values are equal. GCD(a, b) is the number that was discovered after the while loop was terminated. Let’s use the examples of a = 14 and b = 35.

• Iteration 1: We subtract a from b: a = 14 and b = 35-14= 21.
• Iteration 2: We subtract a from b again as a< b: a = 14 and b = 21-14= 7.
• Iteration 3: We subtract b from an as a>b: a = 14-7= 7 and b = 7 We got a = b = 7. Therefore, GCD( 14, 35 )= 7

Code Implementation:

```#include <bits/stdc++.h>
using namespace std;

int main()
{
int a, b, ans;

a=42;
b=63;

int temp1= a, temp2= b;

while(temp1 != temp2) {
if(temp1 > temp2)
temp1 -= temp2;
else
temp2 -= temp1;
}

int gcd= temp1;
ans= a*b / gcd;

cout << " The LCM of " <<a << " and " << b << " is " << ans << endl;

return 0;
}
```

Output:

``The LCM of 42 and 63 is 126``

Time Complexity:
O(max(a, b)): As we know that in each iteration, we are subtracting either a from b or b from a. Hence, we can say max(a, b) iterations will give us the GCD of a and b.

Space Complexity:
O(1) extra space is required as we are using int to save the previously calculated result.

### Method 3 to Find LCM of Two Numbers Using GCD (Recursion)

We can find the LCM of two numbers a and b by using the formula:

LCM(a,b)=a∗b/GCD(a,b)

By subtracting the smaller number from the bigger number between a and b and then recursively sending a and b to the same function, we can use the Euclidean method to get the GCD of a and b.

Code Implementation:

```#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;

// base case
if (a == b)
return a;

// a is greater
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}

int main()
{
int a, b, ans;

a=42;
b=63;

int _gcd = gcd(a,b);
ans= a*b / _gcd;

cout << " The LCM of " <<a << " and " << b << " is " << ans << endl;

return 0;
}
```

Output:

``The LCM of 42 and 63 is 126``

Time Complexity:
O(max(a, b)): As we know that in each recursive call, we are subtracting either a from b or b from a. Hence, we can say max(a, b) iterations will give us the GCD of a and b.

Space Complexity:
O(max(a, b)) extra space is required as total recursive calls are equal to the number of iterations until we get the GCD of the two numbers a and b.

Summary

• The lowest number that is a multiple of both numbers is known as the Least Common Factor (LCF) of two numbers.
• We may use one of two methods to determine the LCM of two numbers:
• by identifying the a and b’s prime factors and then taking the result of combining all of the a and b’s factors.
• Using the formula and the Greatest Common Divisor (GCD),
• LCM(a,b)=a∗b/GCD(a,b)
• We subtract the smaller number from the bigger number until both numbers are equal in order to determine the GCD of a and b.
• We initialize ans with the array’s first element in order to get its LCM, and we then use the array’s ith occurrence of a number to obtain the LCM of ans.

## FAQs related to the C++ Program to Find the LCM of Two Numbers

FAQs related to the C++ program to find the LCM of two numbers are discussed below:

Q1. What are the GCD and LCM of a number?
Ans. The largest positive integer that divides each of two or more non-zero integers is known as the GCD or greatest common divisor. The greatest Common Denominator is another name for GCD. The lowest number (other than zero) that is a multiple of both numbers is known as the least common multiple (LCM) of two numbers.

Q2. What is GCD in C++?
Ans. The greatest number that divides two integers is called the Greatest Common Divisor (GCD).

Q3. Does C++ have a GCD function?
Ans. To get the GCD of two integers, we may alternatively utilize the built-in GCD method C++ __gcd() included in the algorithm header file. Using the GCD function in C++, we compute the GCD of the two user-input values 54 and 22 in the example above.