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

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

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.