C++ Program to Find GCD

To understand this example, you should have the knowledge of the following C++ programming topics:


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.

n1 n2 n1 > n2 n1 -= n2 n2 -= n1 n1 != n2
16 76 false - 60 true
16 60 false - 44 true
16 44 false - 28 true
16 28 false - 12 true
16 12 true 4 - true
4 12 false - 8 true
4 8 false - 4 false

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.

Did you find this article helpful?

Our premium learning platform, created with over a decade of experience and thousands of feedbacks.

Learn and improve your coding skills like never before.

Try Programiz PRO
  • Interactive Courses
  • Certificates
  • AI Help
  • 2000+ Challenges