C++ Program to Find GCD

In the following example of C++ program to find the GCD (greatest common divisor) of two numbers using the Euclidean algorithm :

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

Find HCF/GCD using for loop :

Program :

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

Output :

Enter two numbers: 9
12
HCF = 3

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.

Find GCD/HCF using while loop :

Program :

#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: 6
9
HCF = 3

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.