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.