C++ Program to Find LCM using GCD

by | Jan 26, 2023 | C++, C++ Programs

Home » C++ » C++ Programs » C++ Program to Find LCM using GCD

Introduction

This program will help you find to find the LCM of two positive numbers.

The task is that the user will be asked to enter two integers, and then through this program, the LCM of both numbers will be computed.

LCM: Least Common Multiple.

A positive integer that is perfectly divisible by both numbers without leaving any remainder is the LCM of that number.

A simple formula of mathematics that relates GCD and LCM is

LCM*GCD= n1*n2 (n1 and n2 are the integer values)

We will use this formula in our code to compute the LCM.

To understand this example, you should know about some concepts of C++ programming.

1. Operators

2. for loop

3. if-else statement

4. while and do-while loop

Note: Practice the program to calculate the GCD of two numbers before proceeding further.

Program

#include<iostream>
using namespace std;
int main()
{
int num1, num2;
cout<<"Enter two positive numbers: ";
cin>>num1>>num2;
// we will find a value that divides num1 and num2 completely
int GCD;
for(int i=1; i<=num1 && i<=num2; i++) // 'i' must be less than both of the numbers
{
if (num1%i==0 && num2%i==0) // if 'i' is completely dividing both the numbers
{
GCD=i;
}
}
int LCM=(num1*num2)/GCD; // formula to compute LCM
cout<<"LCM: "<<LCM;
return 0;
}

 

Output

Explanation

In the above program, the user is asked to enter two positive integers, num1 and num2, and the values entered are 50 and 25, respectively.

int GCD; declaration of the ‘GCD’ variable

for(int i=1; i<=num1 && i<=num2; i++)

the above loop will iterate until ‘i’ remains less than equal to both num1 and num2

if (num1%i==0 && num2%i==0)

This condition will get checked in each iteration; if both num1 and num2 are exactly divisible by ‘i’, the value of ‘i’ will be assigned to GCD.

The value of GCD of num1=50 and num=25 is 25

After getting the value of GCD from the above code, we will use the formula to compute the LCM.

int LCM=(num1*num2)/GCD;

LCM=(50*25)/25=50

This is the easiest way to calculate the LCM if and only if we know how to calculate GCD.

 

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Author