This is a simple program to find the Greatest Common Dis. visor (GCD) of two given positive numbers.The program for gcd uses the Euclidean algorithm to compute the results.

More information about the algorithm is given under problem definition section.

This program is written in Dev-C++ version 5( beta) installed on a Windows 7 64-bit machine. Its intended for beginner learner of C programming.

### Problem Definition

Euclidean algorithm is a fundamental algorithm of division. You can read how basic division and Euclidean algorithm related in the following article

C Program to Find Quotient and Remainder

Now, suppose you are given two positive integers, we can use the algorithm to find the gcd number, but we must find the greatest of two numbers. Though in this program we have given the first number as greatest number of two input numbers. If the **a** and **b** are two numbers and **a** is the greatest number, then following is true.

a = q_{0}b + r_{0}

b = q_{1}r_{0} + r_{1}

r_{0 } = q_{2}r_{1} + r_{2}

…………………

…………………

…………………

so on, until **r** is equal to zero.

We can solve for a = 24 and b = 16 using algorithm,

24 = 1 * 16 + 8 16 = 2 * 8 + 0

Since, the remainder value is zero, the gcd value is 8.

**How do we process the input in this program ?**

In this C program to find GCD number, we have given the formula for remainder** r **and if remainder is not equal to 0, call the function **hcf (q _{0}, r)** recursively according to euclidean’ algorithm until remainder

**r = = 0.**

### Flowchart

### Program Code

```
/*Program to find GCD of two number */
#include <stdio.h>
#include <stdlib.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);
}
```