### 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:

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 find 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 . Taking , if the GCD , then the GCD of will be , and the GCD of is , thus for integers the GCD would be .

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 *i ^{th}* iteration.

We find the GCD of the first

*i*integers by and initially .

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