Categories

## 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, NULL, 10); // get values from command line
if (errno != 0 && (b == LONG_MIN || b == LONG_MAX)) // ensure valid input
{
exit(-1);
}

r = strtol(argv, NULL, 10);
if (errno != 0 && (r == LONG_MIN || r == LONG_MAX))
{
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.