Sherlock and GCD
Greatest Common Divisor
The greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder.
The GCD of more than two numbers can be calculated as
GCD(a,b,c) = GCD(GCD(a,b),c)
The most famous method of finding GCD is the Euclidean GCD Algorithm:
Euclidean GCD Algorithm
int gcd(a, b) {
while (b != 0) {
t = b;
b = a % b; \\ a mod b
a = t;
}
return a;
}
Recursive version
int gcd(a, b) {
if (b = 0)
return a
else
return gcd(b, a mod b)
}
Related challenge for Greatest Common Divisor