Euclid’s Algorithm (Greatest Common Divisor) – GCD

Given two non-negative integers a and b. We need to find their greatest common divisor (GCD), ie, the largest number that divides both a and b.

When it is of the numbers is zero, and the other is non-zero, their greatest common divisor, by definition, it is the second number. When both numbers are zero, the result is not defined (any suitable infinite number), we assume in this case the greatest common divisor of zero. Therefore, we can speak of such a rule: if one of the numbers zero, their greatest common divisor is equal to the second number.
Euclid’s algorithm , discussed below, solves the problem of finding the greatest common divisor of two integers a and b over O(log min(a,b)).
This algorithm was first described in the book of Euclid’s “Elements” (about 300 BC), although it is possible that the algorithm has an earlier origin.

Algorithm:

The algorithm is extremely simple and is described by the following formula:

gcd(a,b)  : a  if b=0
	    gcd(b,a mod b), otherwise

Implementation:

int gcd (int a, int b) {
	if (b == 0)
		return a;
	else
		return gcd (b, a % b);
}

Using C ++ ternary conditional operator, the algorithm can be written even shorter:

int gcd (int a, int b) {
	return b ? gcd (b, a % b) : a;
}

Finally, we present and form a non-recursive algorithm:

int gcd (int a, int b) {
	while (b) {
		a %= b;
		swap (a, b);
	}
	return a;
}

Note that this can also be used to find the LCM (Least Common Multiplier) of two numbers a and b, as

LCM(a,b) = a*b / GCD(a,b)

int lcm (int a, int b) {
	return a / gcd (a, b) * b;
}