Gcd (C)

From LiteratePrograms

Other implementations: bc | C

This implements the Euclidean Algorithm in C in two different ways to find the Greatest Common Divisor of two integers 'a' and 'b'.

The first is a recursive definition.

#include <stdio.h>
#include <stdlib.h>
int gcd(unsigned int a, unsigned int b) {
  if(a%b<1) {
    return(b);
  }
  gcd(b,a%b);
}
int main(int argc, char *argv[]) {
  printf("%d\n",gcd(atoi(argv[1]),atoi(argv[2])));
  return(0);
}

The second uses a while loop.

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
  int numerator, denominator, remainder;
  numerator=atoi(argv[1]);
  denominator=atoi(argv[2]);
  while(denominator != 0) {
    remainder   = numerator % denominator;
    numerator   = denominator;
    denominator = remainder;
  }
  printf("%d\n",numerator);
  return(0);
}

Here is yet another implementation that shows each step when computing the Greatest Common Divisor of two integers. This is useful for teaching purposes.

From the Division "Algorithm", we know that: for any integers 'a', and 'b' > 0, there exist integers 'q' and 'r' such that 'q' and 'r' are unique (they are determined by 'a' and 'b') and

The variable 'a,b,q,r' names used here stand for: 'a' usually stands for the numerator of a fraction 'b' usually stands for the denominator of a fraction 'q' for quotient 'r' for remainder

Computing the gcd of two integers using the Euclidean Algorithm makes repeated use of this fact.

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
  int numerator, denominator, quotient, remainder;
  numerator=atoi(argv[1]);
  denominator=atoi(argv[2]);
  printf("a=b*q + r\n");
  while(denominator != 0) {
    quotient    = numerator / denominator;
    remainder   = numerator % denominator;
    printf("%d=%d*%d + %d\n",numerator,denominator,quotient,remainder);
    numerator   = denominator;
    denominator = remainder;
  }
  printf("0=%d*%d + %d -- STOP\n",denominator,quotient,remainder);
  printf("GCD = %d\n",numerator);
  return(0);
}

Download code