C++ Program to Find GCD

The largest integer which can perfectly divide two integers is known as GCD or HCF of those two numbers.

For example, the GCD of 4 and 10 is 2 since it is the largest integer that can divide both 4 and 10. 

Example: 1. Find HCF/GCD using for loop

#include <iostream>
using namespace std;

int main() {
  int n1, n2, hcf;
  cout << "Enter two numbers: ";
  cin >> n1 >> n2;

  // swapping variables n1 and n2 if n2 is greater than n1.
  if ( n2 > n1) {   
    int temp = n2;
    n2 = n1;
    n1 = temp;
  }
    
  for (int i = 1; i <=  n2; ++i) {
    if (n1 % i == 0 && n2 % i ==0) {
      hcf = i;
    }
  }

  cout << "HCF = " << hcf;

  return 0;
}

The logic of this program is simple.

In this program, the smaller integer between n1 and n2 is stored in n2. Then the loop is iterated from i = 1 to i <= n2 and in each iteration, the value of i is increased by 1.

If both numbers are divisible by i then, that number is stored in variable hcf.

This process is repeated in each iteration. When the iteration is finished, HCF will be stored in variable hcf.

Example 2: Find GCD/HCF using while loop

#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;
}

Output

Enter two numbers: 16
76
HCF = 4

In the above program, the smaller number is subtracted from the larger number and that number is stored in place of the larger number.

Here, n1 -= n2 is the same as n1 = n1 - n2. Similarly, n2 -= n1 is the same as n2 = n2 - n1.

This process is continued until the two numbers become equal which will be HCF.

Let us look at how this program works when n1 = 16 and n2 = 76.

Here, the loop terminates when n1 != n2 becomes false.

After the final iteration of the loop, n1 = n2 = 4. This is the value of the GCD/HCF since this is the greatest number that can divide both 16 and 76.

We can also find the GCD of two numbers using function recursion.