Greatest Common Divisor

© Parineeth M R

Question 47. Find the Greatest Common Divisor of two numbers


The Greatest Common Divisor (GCD) of two numbers a and b is the largest number that divides a and b without leaving a remainder. For instance, the GCD of 12 and 20 is 4. It is also called Greatest Common Factor, Highest Common Factor, etc. To find the GCD we use Euclid’s algorithm which is as follows:
gcd(a, 0) = a

gcd(a, b) = gcd(b, a mod b)

So, suppose we have to calculate gcd(12, 20) then we get

gcd(12, 20) = gcd(20, 12 mod 20) = gcd(20, 12)

gcd(20, 12) = gcd(12, 20 mod 12) = gcd(12, 8)

gcd(12, 8) = gcd(8, 12 mod 8) = gcd(8, 4)

gcd(8, 4) = gcd(4, 8 mod 4) = gcd(4, 0) = 4

C/C++


/*
a, b: Two integers. a may be greater than, equal to or less than b
Return value: Greatest common divisor
*/
int gcd(int a, int b)
{
	if (b == 0)
		return a;

	/*Find the GCD of b and the remainder of a/b*/
	return gcd(b, a%b);
}



Java


/*
a, b: Two integers. a may be greater than, equal to or less than b
Return value: Greatest common divisor
*/
public static int gcd(int a, int b) {
	if (b == 0)
		return a;

	/*Find the GCD of b and the remainder of a/b*/
	return gcd(b, a % b);
}



Python


#a, b: Two integers. a may be greater than, equal to or less than b
#Return value: Greatest common divisor
def gcd(a, b) :
	if (b == 0):
		return a

	#Find the GCD of b and the remainder of a/b
	return gcd(b, a % b)