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

1. UVA 11388 – GCD LCM (Analysis)