for code snippets

Saturday, March 12, 2016

Least Common Multiple of Two Numbers

Given Two numbers, say a and b we have to find their lowest multiple which is common to the both nunbers.

Finding Method:
The formula is:
GCD(a,b) * LCM(a,b) = a * b;
Therefore, LCM(a,b) = (a * b) / GCD(a,b);

Code and pitfalls:
int lcm(int a,int b)
{
      return ( a * b ) / gcd ( a, b );
}

this code will work fine but for some cases it may overflow.So we should rewrite the (a*b)/gcd(a,b) part into a/gcd(a,b) * b .

What I use:
template< class T > T lcm(T a, T b) { return (a / gcd(a, b) * b); }

No comments:

Post a Comment