Search

0.5.6.1 Source Code

The algorithm to compute the greatest common divisor presented below was proposed by Euclid in 300 B.C. Historians believe that Euclid did not come up with this on his own but rather recorded an algorithm that was as much as 200 years older. This is the oldest non-trivial algorithm known to exist. Two procedures are included here, a recursive and iterative version.    

void euclid_i (int m, int n) {
    int r;

    while (1) {
      r = m % n;
      if (r == 0) {
        printf("%d\n", n);
        break;
      }
      m = n;
      n = r;
    }
}

void euclid_r (int m, int n) {
    int r;

    r = m % n;
    if (!r) {
      printf("%d\n", n); 
      return;
    }
    euclid_r(n, r);
}

int least_common_mul(int i, int j) {
  return (abs( (i * j) / euclid_i(i, j)));
}