C Program to Find GCD or HCF of Two Numbers

In this video, we will write a C program for finding the HCF of two numbers. The Highest Common Factor is the greatest number that divides each of the two or more numbers. It is also known as Greatest Common Measure (GCM) and Greatest Common Divisor(GCD).

Properties of HCF:
1. Always an HCF of two or more prime numbers is 1.
2. The HCF of two or more numbers divides each of the numbers without a remainder.
3. The HCF of two or more numbers is a factor of each of the numbers.
4. The HCF of two or more numbers is less than or equal to each of the numbers always.

For Example:
HCF of 18 21 30 is 3.
HCF of 5 and 25 is 5.

Here we see two different methodologies to find the HCF of 2 numbers:

1. Using the iterative method:
In this method, we will run a loop backward from the lowest of the 2 numbers to 1. In this loop, if there exists any number which is a divisor of both, it is our desired output. If there does not exist any number, we have 1 as our GCD or HCF as 1 is the divisor of any number.

2. Using the Euclidean formula:
In this method, we will have a call to recursive functions. The base condition is that if the 2 numbers are equal, then any of the numbers is our desired answer. We will call the function again by subtracting smaller numbers from the larger numbers as this does not change the GCD or HCF of that 2 numbers.