The Euclidean Algorithm

Implementation of the Euclidean Algorithm for finding the Greatest Common Divisor of two integers.

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

Please Deposit Two Cents: Cancel reply