# 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.

**GCD**is ” Greatest Common Divisor”. Which means the greatest common factor of the two numbers. It is also known by the name

**HCF**(Highest common factor). I will be using both the words so don’t confuse yourself.

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