[Solved] Greatest common divisor algorithms OTHER than Euclid’s

by


(Note that when computing gcd(a,b), we can assume that a <= b; if that were not true, we could just swap them.)

The Euclidean algorithm is certainly the most efficient way to compute the gcd. But if you need two other (inefficient) ways to compute gcd(a,b), there are plenty:

  1. Starting from a and going down, test every number to see if it divides both a and b.

  2. Prime-factorize a and b (obtaining multisets of primes), and return the product of the intersection of these multisets.

  3. Find all divisors of a, and test if they divide b starting from a and going down.

  4. Find lcm(a,b) by testing which of b, 2*b, 3*b, ... is divisible by a, and return a*b/(lcm(a,b)).

1 and 4 are probably easiest to implement, since they don’t involve factoring.

It’s also important to note some edge cases: gcd(0,x) = x for all x > 0, while gcd(0,0) is undefined. And technically I suppose gcd(a,b) = gcd(abs(a), abs(b)) covers the case where inputs may be negative.

2

solved Greatest common divisor algorithms OTHER than Euclid’s