C++ Programs

C++ Program to Find GCD or HCF of two numbers (4 Ways)

by Amit Rawat · Published May 20, 2019 · Updated May 31, 2019

In this program, we will learn how to find the GCD or HCF of two numbers using the C++ programming language.

The full form of 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:-

Enter two numbers: 45 63
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:-

Enter two numbers: 39 78
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:-

Enter two numbers: 112 48
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;
}