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