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 nontrivial
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)));
}
