C++ Program - Find LCM of Two Numbers

LCM stands for Least Common Multiple. The LCM of two numbers is the smallest number that can be divided by both numbers.

For example - LCM of 20 and 25 is 100 and LCM of 30 and 40 is 120.

Mathematically, LCM of two numbers (a and b) can be expressed as below:

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

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

Method 1: Using For Loop to find GCD and LCM of two numbers

In the example below, for loop is used to iterate the variable i from 1 to the smaller number. If both numbers are divisible by i, then it modifies the GCD and finally gives the GCD of two numbers. GCD of two numbers is then used to calculate LCM of two numbers.

#include <iostream>
using namespace std;

int main() {
  int x = 20;
  int y = 25;
  int temp, gcd, lcm;

  if (x > y) {
    temp = x;
    x = y;
    y = temp;
  }

  for(int i = 1; i < (x+1); i++) {
    if (x%i == 0 && y%i == 0)
      gcd = i;
  }

  lcm = (x*y)/gcd;

  cout<<"LCM of "<<x<<" and "<<y<<" is: "<<lcm;
  return 0;
}

The above code will give the following output:

LCM of 20 and 25 is: 100

Method 2: Using While Loop to find GCD and LCM of two numbers

In the example below, larger number is replaced by a number which is calculated by subtracting the smaller number from the larger number. The process is continued until the two numbers become equal which will be GCD of two numbers. GCD of two numbers is then used to calculate LCM of two numbers.

#include <iostream>
using namespace std;

int main() {
  int p, q, x, y, lcm;
  p = x = 20;
  q = y = 25;
  while (x != y) {
    if (x > y)
      x = x - y;
    else
      y = y - x;
  }

  lcm = (p*q)/x;

  cout<<"LCM of "<<p<<" and "<<q<<" is: "<<lcm;
  return 0;
}

The above code will give the following output:

LCM of 20 and 25 is: 100

Method 3: Using the recursive function to find GCD and LCM of two numbers

In the example below, recursive function is used which uses Euclidean algorithm to find GCD of two numbers which is further used to calculate LCM of two numbers.

#include <iostream>
using namespace std;

int gcd(int x, int y) {
  if (y == 0)
    return x;
  return gcd(y, x%y);
}

int main() { 
  int x = 30;
  int y = 40;

  int lcm = (x*y)/gcd(x,y);

  cout<<"LCM of "<<x<<" and "<<y<<" is: "<<lcm;
  return 0;
}

The above code will give the following output:

LCM of 30 and 40 is: 120

Method 4: Using __gcd() function of <algorithm> header file

C++ has built-in function __gcd() in <algorithm> header file which can be used to calculate LCM of two numbers. The syntax for using this function is given below:

//returns 0 if both x and y are zero,
//else returns gcd of x and y
__gcd(x,y);

Consider the following example:

#include <iostream>
#include <algorithm>
using namespace std;

int main() { 
  int x = 100;
  int y = 150;
  int lcm;

  lcm = (x*y)/__gcd(x,y);

  cout<<"LCM of "<<x<<" and "<<y<<" is: "<<lcm;
  return 0;
}

The above code will give the following output:

LCM of 100 and 150 is: 300