Problem
Given two number A and B, find their lowest common multiple (LCM).
We are trying to find the LCM of A and B. What is LCM? It is the smallest positive number which is divisible by both A and B.
How do we find it?
It is based on the formula that, $LCM(A,B) \times GCD(A,B) = A \times B$. How did we get this formula? I will discuss it another day. It's not that hard to figure out though. Anyways, from that formula we can derive $LCM(A,B) = \frac{A \times B}{GCD(A,B)}$.
For example, $LCM(6,15) = \frac {(6 \times 15 )}{GCD(6,15)}= \frac{90}{3} = 30$, $LCM(3,4)= \frac{3 \times 4 }{GCD(3,4)} = \frac{12}{1} = 12$.
Code and Pitfalls
Let us try to convert the above equation for LCM to code. If we convert exactly like the equation, code would be something like the following:
int lcm ( int a, int b ) {
return ( a * b ) / gcd ( a, b );
}
This will work, but for some cases this code will overflow. For example, if we try to find $LCM( 2^{20}, 2^{15})$, it is obvious that the LCM is $2^{20}$. But notice what happens when we follow the algorithm. We first try to multiply $2^{20}$ with $2^{15}$, which results in $2^{35}$ which is too big to fit in an "int" variable. It overflows, and returns us wrong answer. But the LCM itself should fit in the "int" variable easily.
A better way to write the above code is using the following observation. $LCM(A,B) = \frac{A \times B}{GCD(A,B)} = \frac{A}{GCD(A,B)} \times B$. Since $GCD(A,B)$ divides both A and B, the fraction $ \frac{A}{GCD(A,B)}$ will be an integer. This alternate equation avoids overflow since instead of multiplying A and B, it first reduces A to a smaller number and multiplies the resultant number with B. So, if $LCM(A,B)$ fits in "int" variable, then we will get it without the risk of intermediate products overflowing.
int lcm ( int a, int b ) {
return ( a / gcd ( a, b ) ) * b;
}
Related Problems
Labels: LCM, Number Theory