Given two non-negative integers a and b, we have to find their GCD (greatest common divisor), i.e. the largest number which is a divisor of both a and b. It's commonly denoted by gcd(a,b). Mathematically it is defined as:
gcd(a,b)=maxk=1…∞ : k∣a ∧k ∣bk.
When one of the numbers is zero, while the other is non-zero, their greatest common divisor, by definition, is the second number. When both numbers are zero, their greatest common divisor is undefined (it can be any arbitrarily large number), but we can define it to be zero. Which gives us a simple rule: if one of the numbers is zero, the greatest common divisor is the other number.
The Euclidean algorithm, discussed below, allows to find the greatest common divisor of two numbers a and b in O(logmin(a,b)).
The algorithm was first described in Euclid's "Elements" (circa 300 BC), but it is possible that the algorithm has even earlier origins.
int gcd (int a, int b) {
if (b == 0)
return a;
else
return gcd (b, a % b);
}
int gcd (int a, int b) {
return b ? gcd (b, a % b) : a;
}
int gcd (int a, int b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
int lcm (int a, int b) {
return a / gcd(a, b) * b;
}