C++ Program to Find GCD or HCF of two numbers (4 Ways)
In this program, we will learn how to find the GCD or HCF of two numbers using the C++ programming language.
We will discuss four ways to write code for it.
- Using While loop
- Using for loop
- Using Euclid Algorithm
– Using While loop
– Using Recursion
C++ Programming Code to Find GCD or HCF of two numbers
Using While loop
Code:-
#include <iostream> using namespace std; int main() { int num1, num2, gcd; cout << "Enter two numbers: "; cin >> num1 >> num2; while(num1 != num2){ if(num1 > num2) num1 -= num2; else num2 -= num1; } cout << "GCD is " << num1 << endl; return 0; }
Output:-
GCD is 9
Using For Loop
We have checked both numbers by dividing them every number less than the minimum of both the numbers. And if that number divides both the numbers without leaving any remainder than that number becomes the HCF of the given numbers. And remember that I am running the loop in reverse order.
Code:-
#include <iostream> using namespace std; int main() { int num1, num2, gcd; cout << "Enter two numbers: "; cin >> num1 >> num2; for (int i = min(num1, num2); i > 0; i--) { if (num1 % i == 0 && num2 % i ==0) { gcd = i; break; } } cout << "GCD of " << num1 << " and " << num2 << " is " << gcd << endl; return 0; }
Output:-
GCD of 39 and 78 is 39
Using Euclid Algorithm
What is Euclid Algorithm?
The Euclid Algorithm for finding getGCD(A,B) is as follows:
- If A = 0 then getGCD(A,B)=B, since the getGCD(0,B)=B, and we can stop.
- If B = 0 then getGCD(A,B)=A, since the getGCD(A,0)=A, and we can stop.
- Write A in quotient remainder form (A = B⋅Q + R)
- Find getGCD(B,R) using the Euclidean Algorithm since getGCD(A,B) = getGCD(B,R)
Using While Loop
Code:-
#include <iostream> using namespace std; int main() { int num1, num2, temp; cout << "Enter two numbers: "; cin >> num1 >> num2; while (num1%num2 != 0){ temp = num1; num1 = num2; num2 = temp%num2; } cout << "HCF is " << num2 << endl; return 0; }
Output:-
HCF is 16
Using Recursion
Code:-
#include <iostream> using namespace std; int gcd(int num1, int num2) { if (num2 == 0) return num1; return gcd(num2, num1 % num2); } int main() { int num1, num2; cout << "Enter two numbers: "; cin >> num1 >> num2; cout << "HCF is " << gcd(num1, num2) << endl; return 0; }
Output:-
HCF is 2
You can learn about many other C++ Programs Here.
Best Books for learning C++ programming language with Data Structure and Algorithms.
Amit Rawat
Latest posts by Amit Rawat (see all)
- Python Program to Print the Fibonacci Sequence (2 ways) - April 7, 2020
- Python Program to Display or Print Prime Numbers Between a Range or an Interval - June 18, 2019
- Python Program To Print Pascal’s Triangle (2 Ways) - June 17, 2019