# C Program to find GCD or HCF Of Two Numbers

## Write a C program to find GCD or HCF of Two Numbers

The Highest Common Multiple or the Greatest Common Divisor is the greatest number that exactly divides both numbers. It is possible to calculate this number through simple mathematical calculations. The following algorithm shows how the GCD of two numbers is calculated.

Ex:-

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. Enter two numbers a and b.

Step 3. If a = 0, return b.

Step 4. If b = 0, return a.

Step 5. If a is equal to b return a

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

Step 7. Else return a, b-a

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