This post regards the Euclidean Algorithm for determining the Greatest Common Divisor (GCD) of two integers.

I happened to read about this fun and simple algorithm and decided since I’ve been doing some C programming to take a little time to implement this in C. The version below outputs to the console via printf, but could easily be modified to return a value and thus be used as part of other programs.

Here it is:

[snip out GPL notice, it's in the actual file though] #include <stdio .h> #include <stdlib .h> #include <limits .h> #include <errno .h>

int main(int argc, char **argv) { int a,b,r; // declare variables

if (argc < 3) { printf("usage: gcd <value> <value> where neither == 0\n"); exit(-1); }

b = strtol(argv[1], NULL, 10); // get values from command line if (errno != 0 && (b == LONG_MIN || b == LONG_MAX)) // ensure valid input { perror("Bad argument"); exit(-1); }

r = strtol(argv[2], NULL, 10); if (errno != 0 && (r == LONG_MIN || r == LONG_MAX)) { perror("Bad argument"); exit(-1); }

if (b < r) // order them properly { a = r; r = b; b = a; }

while (r != 0) // keep going until GCD found (worst case it's 1) { a = b; // shuffle values to correct spots b = r;

if ((r = a % b) == 0) // compute the remainder, if it's 0 then GCD found { printf("The GCD is: %d\n", b); exit(0); } } printf("usage: gcd <value> <value> where neither == 0\n"); exit(-1); }

If I’ve made any grievous errors or there’s just a better way please let me know. This code is released under the GPL.

Also, you can download this file here: gcd.c

An example of input/output:

./gcd 184965 385

The GCD is: 55