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.

1 2 3 4 5 6 7 8 9 10 11 |
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); } |