# C Program to find GCD or HCF Of Two Numbers

## GCD or HCF of Two numbers in C

Here, in this section we will discuss GCD or HCF of two numbers in C. The Highest Common Multiple or the Greatest Common Divisor is the greatest number that exactly divides both numbers.

There are many methods to calculate GCD:

• Using Prime Factorisation,
• Euclid’s Algorithm,
• Lehmer’s GCD algorithm, etc

It is possible to calculate this number through simple mathematical calculations. The following algorithm shows how the GCD of two numbers is calculated.

Example:-

The H.C.F or G.C.D of 12 and 14 is 2.

The H.C.F or G.C.D of 16 and 12 is 4 ## Working:-

Step 1. Start

Step 2. Take two integers numbers from the user and store them in variable say a and b.

Step 3. Create a function say gcd() that take two parameters as arguments.

Step 4. Inside function, if a = 0, return b.

Step 5. If b = 0, return a.

Step 6. If a is equal to b return a

Step 7. If a is greater than b, return a – b, and b

Step 8. Else return a, b-a

Step 9. Call function gcd() recursively.

Step 8. Stop   ## C program to calculate GCD of two numbers

```// C program to calculate GCD of two numbers
#include<stdio.h>
// The code used a recursive function to return gcd of p and q
int gcd(int p, int q)
{

// checking divisibility by 0
if (p == 0)
return q;
if (q == 0)
return p;

// base case
if (p == q)
return p;
// p is greater
if (p > q)
return gcd(p-q, q);

else
return gcd(p, q-p);
}

// Driver program to test above function
int main()
{     int p = 98, q = 56;
printf("GCD of %d and %d is %d ", p, q, gcd(p, q));
return 0;
}

```

## Output

```The GCD of 98 and 56 is 14.
```