C++ Program to Find GCD

C++ program to find GCD or HCF

In this example, you will learn about different ways of C++ program to find GCD or HCF using for and while loop of two integers.

The largest number that can perfectly divide both numbers is known as Greatest Common Divisor (GCD) or Highest Common Factor (HCF).

There are many ways to find GCD. In this article, we will discuss two simple logic.

Source Code :

#include <iostream>
using namespace std;
int main()
{
    int n1, n2;
    cout << "Enter two numbers: ";
    cin >> n1 >> n2;
    
    while(n1 != n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    cout << "HCF = " << n1;
    return 0;
}

Enter two numbers: 78 52 HCF = 26

The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both of them.

For example: Let’s say we have two numbers are 45 and 27.

45 = 5 * 3 * 3
27 = 3 * 3 * 3

So, the GCD of 45 and 27 is 9.

A program to find the GCD of two numbers is given as follows.

Example

#include <iostream>
using namespace std;
int gcd(int a, int b) { 
   if (b == 0) 
      return a; 
   return gcd(b, a % b);  
} 
int main() { 
   int a = 105, b = 30; 
   cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b); 
   return 0; 
}   

Output

GCD of 105 and 30 is 15

In the above program, gcd() is a recursive function. It has two parameters i.e. a and b. If b is greater than 0, then a is returned to the main() function. Otherwise the gcd() function recursively calls itself with the values b and a%b. This is demonstrated by the following code snippet −

int gcd(int a, int b) { 
   if (b == 0) 
      return a; 
   return gcd(b, a % b);  
}

Another program to find the GCD of two numbers is as follows −

Example

#include<iostream>
using namespace std;
int gcd(int a, int b) { 
   if (a == 0 || b == 0) 
      return 0; 
   else if (a == b) 
      return a; 
   else if (a > b) 
      return gcd(a-b, b); 
   else return gcd(a, b-a); 
} 
int main() { 
   int a = 105, b =30; 
   cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b); 
   return 0; 
} 

Output

GCD of 105 and 30 is 15

In the above program, gcd() is a recursive function. It has two parameters i.e. a and b. If a or b is 0, the function returns 0. If a or b are equal, the function returns a. If a is greater than b, the function recursively calls itself with the values a-b and b. If b is greater than a, the function recursively calls itself with the values a and (b - a). This is demonstrated by the following code snippet.

int gcd(int a, int b) { 
   if (a == 0 || b == 0) 
      return 0; 
   else if (a == b) 
      return a; 
   else if (a > b) 
      return gcd(a - b, b); 
   else return gcd(a, b - a); 
}