RUN

# Program to find LCM and GCD/HCF of two numbers in C++

Written By -

The highest common factor is also known as GCD (Greatest common divisor). GCD is the largest possible integer which can be divided by the given numbers without a remainder.

Note: GCD is also known as HCF(Highest Common Factor).

LCM, lowest common multiple is the least possible integer which can be divided by the given numbers without a remainder.

In the example given below, we will take two numbers and find their GCD and LCM.

### Logic:

For GCD:

We will take a number, check if it is perfectly divisible by both numbers. We store the value in a variable, and then, print the variable.

For LCM:

We use a formula here,

LCM = Num1*Num2/GCD

Algorithm:

1. Take two number’s as input.
2. Check if the given numbers are divisible by any number less than the number itself using for loop.
3. If yes, then store it (in gcd) and continue ahead.
4. After termination of the loop, the last updated value in gcd will be GCD.
5. To find LCM of the numbers apply the formula for lcm.
6. Now, Print the GCD and LCM

Code:

``````#include<iostream>
using namespace std;
int main()
{
int fnum,snum,gcd,lcm;
cout<<"Enter first number";
cin>>fnum;
cout<<"\nEnter second number";
cin>>snum;
//find factors of both numbers
for(int i=1;i<=fnum && i<=snum;i++)
{
if(fnum%i==0 && snum%i==0)
gcd=i;
}
//find lcm of both numbers
lcm = fnum*snum/gcd;
cout<<"\n GCD of given numbers is:"<<gcd;
cout<<"\n LCM of given numbers is:"<<lcm;
return 0;
}``````

Output:

``````Enter first number 10
Enter second number 5
GCD of given numbers is:5
LCM of given numbers is:10``````

Related Posts:

Tutorials

Examples

Online Compilers

Interview Questions

Recent Articles