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