This is a simple program to find the Greatest Common Divisor (GCD) of two given positive numbers.

We wrote and compiled the program on Dev-C++ version 5( beta) compiler installed on a Windows 7 64-bit machine. If you want to try a different C compiler, make sure to modify the existing source code to get an error-free program.

Learn following c programming topics before you try the example program.

## Problem Definition

Suppose you want to find **GCD **of two numbers – a and *b*. The C program for **GCD **has a function called hcf(a, b) which is called recursively until remainder is 0. The function uses the following logic on the given input numbers where a is greater than or equal to b.

\begin{aligned} &r = a - (a/b * b) \end{aligned}

Suppose and than

\begin{aligned} &r = 24 - (24/6 * 6)\\ &r = 24 - 24 = 0\\ &r = 0 \end{aligned}

Then the value of is the **GCD **which is . Note: – number must be greater than or equal to .

## Flowchart – Program for GCD of Two Numbers

## Program Code – Program for GCD of Two Numbers

```
#include <stdio.h>
#include <conio.h>
main()
{
int i,a,b,gcd;
int hcf();
/* Read the input numbers */
printf("Enter Two Numbers To Find GCD:");
scanf("%d%d",&a,&b);
/* Compute the GCD for given numbers */
gcd=hcf(a,b);
/* Print the Result */
for(i=0;i<40;i++)
printf("_");printf("\n\n");
printf("GCD of %d and %d is %d\n",a,b,gcd);
for(i=0;i<40;i++)
printf("_");printf("\n\n");
system("PAUSE");
return 0;
}
int hcf(p,q)
{
int r;
r=p-(p/q*q);
if(r==0)
return(q);
else
return hcf(q,r);
}
```

The important piece of code in the above source code is the call to function and the function calling itself recursively.

`gcd = hcf(a, b);`

The function evaluate the current value of and , and if the remainder is not equal to , it call itself one more time until the remainder becomes .

```
int hcf(p,q)
{
int r;
r=p-(p/q*q);
if(r==0)
return(q);
else
return hcf(q,r);
}
```

## Output

The output of the program is given below. When the user enters and , the result is which greatest common divisor (GCD) of and .

```
Enter Two Numbers To Find GCD:24 6
------------------------------------------
GCD of 24 and 6 is 6
------------------------------------------
```