The Euclidean Algorithm

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