GCD (Greatest Common Divisor)
I would usually approach something like GCD but prime fatoring both numbers and then multiply the matching prime factors. This will work, but it turns out that a much easier method exists.The Euclidean algorithm is a very simple and fast algorithm for finding GCD. The original algoritm is based on repeated subtractions, but an improvement is to use the modulo (%) operation.
- Assume a and b are two positive integers that you wish to discover the GCD of
- Ensure that a > b (if not swap them)
- If a % b == 0 is zero, then b is the GCD
- else, retry GCD b and a % b
- Repeat until a remainder of 0 (in which case the value of b is the GCD
int gcd(int a, int b)
{ /* FUNCTION gcd */
/* this uses Euclid's method */
int toReturn;
if (0 == b)
toReturn = a;
else
toReturn = gcd(b, (a % b));
return toReturn;
} /* FUNCTION gcd */