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.

Example: C++ program to find GCD or HCF using for loop

//C++ program to find greatest common divisor (GCD)
#include <iostream>
using namespace std;

int main()
{
   int x, y, i, gcd;

   cout << "Enter two integer values:" << endl;
   cin >> x >> y;

   for (i = 1; i <= x && i <= y; i++)
   {
      if (x % i == 0 && y % i == 0)
         gcd = i;
   }

   cout << "\nGCD of " << x << " and " << y << " is: " << gcd << endl;

   return 0;
}

Output
C++ program to find GCD or HCF - Output

Explanation
The value of i is increased till it is equal to x or y.

In every iteration, if condition checks whether x and y are both perfectly divisible by i or not.

If x and y are perfectly divisible then the value of i is stored in gcd.

Example: C++ program to find GCD or HCF using while loop

//C++ program to find GCD or HCF using while loop
#include <iostream>
using namespace std;

int main()
{
   int x, y, temp, gcd;

   cout << "Enter two integer values:" << endl;
   cin >> x >> y;

   //while loop for calculation of GCD
   while (y != 0)
   {
      temp = y;
      y = x % y;
      x = temp;
   }

   gcd = x;
   cout << "\nGCD or HCF of given numbers: " << gcd << endl;

   return 0;
}

Output

aEnter two integer values:
96
108
GCD or HCF of given numbers: 12

Explanation
In the above program, while loop continues till y is not equal to zero.

The value of y is calculated as x % y.