GCD and LCM / Boyan Mihaylov

GCD (Greatest Common Divisor) of two non-zero integers, is the largest positive integer that divides both numbers without remainder. For example, the GCD of the number 10 and 25 is 5 (10 = 5*2 and 25 = 5*5).

LCM (Least Common Multiple) of two integers a and b is the smallest positive integer that is a multiple of both a and b. Since it is a multiple, a and b divide it without remainder. If there is no such positive integer, e.g., if a = 0 or b = 0, then LCM is defined to be zero.

There is a connection between GCD and LCM and here it is: GCD(a, b) * LCM(a, b) = a*b

I will show you a simple implementation of the Euclid’s algorithm to determine the GCD of two integers. After you find the GCD of those two integers, you can find the LCM of them, too.

public int GreatesCommonDivisor(int firstNum, int secondNum)
{
	if (secondNum == 0) return firstNum;

	return GreatesCommonDivisor(secondNum, firstNum % secondNum);
}

public int LeastCommonMultiple(int firstNum, int secondNum)
{
	return (firstNum * secondNum) / GreatesCommonDivisor(int firstNum, int secondNum);
}

public int GreatesCommonDivisor(int firstNum, int secondNum)

{

if (secondNum == 0) return firstNum;

return GreatesCommonDivisor(secondNum, firstNum % secondNum);

}

public int LeastCommonMultiple(int firstNum, int secondNum)

{

return (firstNum * secondNum) / GreatesCommonDivisor(int firstNum, int secondNum);

}