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(a*b) 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(a*b).

**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.