C++ Program to find the LCM of two numbers

June 16, 2023

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.

LCM of two numbers in C++

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<bits/stdc++.h>
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

Highest Common Factor(HCF)

 

Binary to Decimal to conversion

Octal to Decimal conversion

Hexadecimal to Decimal conversion

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

Prime Course Trailer

Related Banners

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

Get Prime
While loop in C

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);

    }