Tutorials
Examples
Tests

# C++ Program to Find LCM and HCF (GCD) of Two Numbers

In this article, you will learn and get code to find and print LCM and HCF (GCD) of any given two numbers by user at run-time in C++. Here are the list of programs, you will go through:

• Find LCM of Two Numbers using while Loop
• Find HCF of Two Numbers using while Loop
• Find LCM and HCF of Two Numbers in Single Program. Code used in this program is most preferred one to find LCM and HCF both
• Find LCM and HCF of Two numbers using for loop
• using Function

### How to LCM and HCF get Calculated ?

Before going through programs listed above, if you're not aware about, how LCM or HCF of two numbers gets calculated, then you can refer to these articles:

to clear all your doubt about LCM and HCF. Now let's move on to the program.

## C++ Find LCM of Two Numbers

To find the LCF of two numbers in C++ programming, you have to ask from user to enter the two number. Then find and print its LCM on output as shown in the program given below.

Note - LCM is the Lowest Common Multiple or Least Common Divisor. For example, if there are two numbers say 10 and 12. Then its Least Common Divisor is 60. That is, both numbers 10 and 12 divides 60 without leaving any remainder (or with leaving 0 as remainder).

```#include<iostream>
using namespace std;
int main()
{
intnumOne, numTwo, mp;
cout<<"Enter Two Numbers: ";
cin>>numOne>>numTwo;
if(numOne>numTwo)
mp = numOne;
else
mp = numTwo;
while(1)
{
if((mp%numOne == 0) && (mp%numTwo == 0))
break;
else
mp++;
}
cout<<"\nLCM ("<<numOne<<", "<<numTwo<<") = "<<mp;
cout<<endl;
return 0;
}```

This program was build and run under Code::Blocks IDE. Here is its sample run:

Now supply any two numbers say 2 and 3. Press `ENTER` key to find and print its LCM as shown in the output given below:

Note - 6 is the lowest number that is completely divisible by both numbers 2 and 3.

Here is another sample run with user input, 4, 5:

The main logic behind above program is:

• Initializes the greater number to mp
• Putting 1 as condition of while loop always evalautes to be true. Therefore this loop ends its executing until the break keyword gets executed
• The break keyword gets executed when both the condition of if (inside while loop) evaluates to be true
• Every time entering into while loop's body, a condition is applied using if, that checks whether the value in mp is divisible by both the number or not
• If it is divisible, then use break keyword and exit from the loop
• Otherwise increment its value and continue to check with next

The dry run of above program with user input 2 and 3 goes like:

• When user enters 2 and 3 as input. Then it gets stored in numOne and numTwo variables. So, numOne=2 and numTwo=3
• Now the condition of if gets executed. That is, the condition numOne>numTwo or 2>3 evaluates to be false, therefore program flow does not goes inside if's body, rather it goes to its else's part, and the value of numTwo gets initialized to mp. So mp=3
• Now the condition 1 (of while loop), evaluates to be true, therefore program flow goes inside the loop
• Inside the loop, the condition of if gets evaluated. That is the condition, mp%numOne==0 or 3%2==0 or 1==0 evaluates to be false. Because the first condition evaluates to be false, therefore no need to evaluate the second condition
• So the value of mp gets incremented and checks for the condition again with new value of mp, that is 4 for second time here
• This process continues until both conditions evaluates to be true, and program flow goes inside if's body, executes the break keyword to stop the execution of while loop
• When the value of mp becomes 6, then both the condition satisfies, that is 6 is divisible by both numbers say 2 and 3
• Therefore after exiting from the loop, the value of mp will be 6.
• Print the value of mp as LCM result of given two numbers.

## C++ Find HCF (GCD) of Two Numbers

Unlike LCM, that deals multiple (lowest common), HCM deals with factor (highest common). HCF can be called as Highest Common Factor, or Greatest Common Factor (GCD).

For example, if there are two numbers say 10 and 12, then its highest common factor is 2. That is, 2 is the highest number that divides both the number. 1 also divides both numbers, but 2 is greater, so 2 is HCF of 10 and 12.

The question is, write a program in C++ that finds HCF of two numbers. Here is its answer:

```#include<iostream>
using namespace std;
int main()
{
intnumOne, numTwo, mp;
cout<<"Enter Two Numbers: ";
cin>>numOne>>numTwo;
if(numOne<numTwo)
mp = numOne;
else
mp = numTwo;
while(1)
{
if((numOne%mp == 0) && (numTwo%mp == 0))
break;
else
mp--;
}
cout<<"\nHCF ("<<numOne<<", "<<numTwo<<") = "<<mp;
cout<<endl;
return 0;
}```

Here is its sample run with user input, 2 and 3:

Note - Because 1 is the highest positive integer that divides both the number say 2 and 3, therefore 1 is the HCF of 2 and 3

Note - Here, highest positive integer, must be less than the smaller number of given two numbers.

Here is another sample run with user input, 18 and 27:

Note - Because 9 is the highest positive integer that divides both the number say 18 and 27

The logic used here is little similar to previous program on LCM of two numbers. The difference is in the condition and the update of mp variable. That is, instead of incrementing it, decrement its value every time entering into the loop. And the condition gets changed with:

`if((numOne%mp == 0) && (numTwo%mp == 0))`

## C++ LCM and HCF in One Program

This C++ program receives two numbers from user and finds both LCM and HCF.

```#include<iostream>
using namespace std;
int main()
{
intnumOne, numTwo, lcm, hcf, a, b, temp;
cout<<"Enter Two Numbers: ";
cin>>numOne>>numTwo;
a = numOne;
b = numTwo;
while(b!=0)
{
temp = b;
b = a%b;
a = temp;
}
hcf = a;
lcm = (numOne*numTwo)/hcf;
cout<<"\nLCM ("<<numOne<<", "<<numTwo<<") = "<<lcm;
cout<<"\nHCF ("<<numOne<<", "<<numTwo<<") = "<<hcf;
cout<<endl;
return 0;
}```

Here is its sample run with user input, 9, 8:

## C++ Find LCM and HCF of Two Numbers using for Loop

Now let's create the same program using for loop

```#include<iostream>
using namespace std;
int main()
{
intnumOne, numTwo, mp, temp;
cout<<"Enter Two Numbers: ";
cin>>numOne>>numTwo;
if(numOne>numTwo)
mp = numOne;
else
mp = numTwo;
temp = mp;
for(;;mp++)
{
if((mp%numOne == 0) && (mp%numTwo == 0))
break;
}
cout<<"\nLCM ("<<numOne<<", "<<numTwo<<") = "<<mp;
mp = temp;
for(;;mp--)
{
if((numOne%mp == 0) && (numTwo%mp == 0))
break;
}
cout<<"\nHCF ("<<numOne<<", "<<numTwo<<") = "<<mp;
cout<<endl;
return 0;
}```

Here is its sample run with user input, 10 and 12:

Note - The initialization part (first part) and condition-checking part (second part) of for loop is hidden. Leaving the condition empty, always evaluates to be, as true condition.

## C++ Find LCM and HCF of Two Numbers using Function

This program uses two user-defined functions namely, findLCM() and findHCF() to find LCM and HCF of two entered numbers by user.

Both function receives two arguments, as first and second number, returns LCM/HCF of these two numbers passed as its argument.

```#include<iostream>
using namespace std;
int findLCM(int, int);
int findHCF(int, int);
int main()
{
intnumOne, numTwo, res;
cout<<"Enter Two Numbers: ";
cin>>numOne>>numTwo;
res = findLCM(numOne, numTwo);
cout<<"\nLCM ("<<numOne<<", "<<numTwo<<") = "<<res;
res = findHCF(numOne, numTwo);
cout<<"\nHCF ("<<numOne<<", "<<numTwo<<") = "<<res;
cout<<endl;
return 0;
}
int findLCM(int a, int b)
{
intlcm;
if(a>b)
lcm = a;
else
lcm = b;
while(1)
{
if((lcm%a == 0) && (lcm%b == 0))
break;
lcm++;
}
return lcm;
}
int findHCF(int a, int b)
{
inthcf;
if(a>b)
hcf = a;
else
hcf = b;
while(1)
{
if((a%hcf == 0) && (b%hcf == 0))
break;
hcf--;
}
return hcf;
}```

Here is its sample run with user input, 6, 8:

#### Same Program in Other Languages

C++ Online Test

« Previous Program Next Program »