### Greatest Common Divisor

Let a and b be integers, not both zero. The largest integer d such that d exactly divides both a and b is called the greatest common divisor of a and b . The GCD of the two integers a and b is denoted as gcd(a, b)

### The Process

This implementation would follow the Euclid’s Algorithm. The gcd function for two integers is as shown below:

$gcd (a, 0) = a$
$gcd (a, b) = gcd (b, a\mbox{ mod }b)$

First we divide a with b and get the remainder r . If r is 0 then b is the GCD as it exactly divides a and obviously itself, else r might be the GCD in which case r should divide b exactly. To test for this in the next iteration the new value of a is the old value of b from the old iteration, and the new value of b is the value of r from the previous iteration. Thus the process continues while r is not 0. When r is zero that is b exactly divides a and thus b has the GCD of the initial two integers. The process to find the GCD of two integers is as below:

```INTEGER a, b, r;
WHILE TRUE , run loop forever
r = a%b
IF 'r' = '0'
THEN
BREAK from loop
ENDIF
a = b
b = r
ENDWHILE
Now b is the GCD of the two initial integers.
```

This process is used to determine the GCD of n integers. Let there be n integers  $a_0, a_1, a_2, a_3, a_4, \ldots , a_n$. Taking $g_0 = 0$, if the GCD $g_1 = gcd (g_0, a_0)$, then the GCD of $a_0, a_1$ will be $g_2 = gcd (g_1, a_1)$, and the GCD of $a_0, a_1, a_2$ is $g_3 = gcd (g_2, a_2)$, thus for $n$ integers the GCD would be $g_n = gcd ( \ldots gcd(gcd(gcd(gcd(g_0, a_0), a_1), a_2), a_3), \ldots , a_{n-1}))$.
This is implemented by taking one variable used to hold the intermediate GCD values and another the input numbers. The intermediate GCD value is set to 0, and the next input number and the current intermediate GCD result is processed and the next GCD is found. This is performed iteratively and at ith iteration.
We find the GCD of the first i integers by $g_i = gcd (g_{i-1}, a_{i-1})$ and initially $g_0 = 0$.

### Sourcecode

```#include <stdio.h>

#define TRUE 1

int gcd (int a, int b);

int
main (void)
{
int g = 0, a, i = 0;
printf ("\nFinding GCD of n integers");
printf ("\nEnter numbers serially (\"0\" to end)\n");

while (TRUE)
{
printf ("Enter Number [%d] :", i++);
scanf ("%d", &a);
/* 0 to end */
if (a == 0)
break;
/* a is used to hold the temporary value of
*     * gcd at ith iteration
*         */
g = gcd (g, a);
}
printf ("\nGCD is %d\n", g);

return 0;
}

int
gcd (int a, int b)
{
int rem;

if (b == 0)
return a;

while (TRUE)
{
rem = a % b;
if (rem == 0)
break;
a = b;
b = rem;
}
return b;
}
```

g is initialized to 0 which would be used to hold intermediate GCD results. The integers are input inside the loop and the GCD of the currently input integer a with the old value of g is found and the value of g is updated with this result which reflects the GCD of the all input integers till now. When 0 is input the loop is terminated. The function GCD is coded following the exact structure of the algorithm.

### Output

Run 1:       input = 35, 95, 215, 65

```Finding GCD of n integers
Enter       numbers      serially    ("0"  to  end )
Enter       Number     [1]   :35
Enter       Number     [2]   :95
Enter       Number     [3]   :215
Enter       Number     [4]   :65
Enter       Number     [5]   :0
GCD is       5
```

Run 2:       input = 221, 39, 4199, 247, 91

```Finding GCD of n integers
Enter numbers serially ("0"  to  end )
Enter       Number     [1]   :221
Enter       Number     [2]   :39
Enter       Number     [3]   :4199
Enter       Number     [4]   :247
Enter       Number     [5]   :91
Enter       Number     [6]   :0
GCD is       13
```

### Resources

Check more about GCD/HCF/GCF in wikipedia: http://en.wikipedia.org/wiki/Greatest_common_divisor

###### Update

27.03.2011 : Code slightly changed. gcd () function now safe from division by 0
07.05.2011 : Code updated, slight modification in iterative function.