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.