95

7
Q:

## Least Common Multiple of given numbers

Whats the simple logic for calculating LCM of given numbers?

+2  A:

You compute first the GCD via Euclid's Algorithm (google) then use gcd(a,b) * lcm(a,b) = a*b, but beware of overflows.

A:

Decompose each number into a series of prime numbers that are multiplied together. Eliminate any primes in the first series that also occur in the second. Multiply together everything that remains.

A different explanation of this method can be found on Wikipedia.

+1  A:

+2  A:

the LCM(a,b) = abs(a * b) / gcd(a, b)

and gcd algorithm goes there:

``````gcd(a, b):
if b = 0
return a
else
return gcd(b, a % b)
``````
abs will work or not
why not? are you having some trouble with this? the "%" is java (not sure about C++, probably the same) is not real mod(%), if "a" is negative, the value might not be what you want.
A:

A good approach, unsuitable with big numbers, is to exploit properties of GCD together with the LCM:

``````int lcm(int a, int b)
{
return (a*b)/gcd(a,b);
}
``````

where you can use the Euclidean Algorithm to find GCD easily:

``````int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a%b);
}
``````

(of course this algorithm can be expressed also in an iterative way, you can easily search for it on google or try it yourself..)

Using (a*b) is overflow prone.
A:

Here is a way to think of it:

The least common multiple contains all those factors which are in both a and b, but not duplicated.

Greatest common divisor contains all the factors common to both a and b, those which would otherwise be duplicated.

LCM(a,b) = (factors only in a) * (factors only in b) * (factors in both a and b)
LCM(a,b) = (a / GCD(a,b)) * (b / GCD(a,b)) * GCD(a,b)
LCM(a,b) = (a / GCD(a,b)) * b

This formulation calculates intermediate values which are less than `a * b`, so it is less prone to overflow than `(a * b)/GCD(a,b)`.

A:

If h is the HCF (same as GCD) of a and b, then the LCM m is given by

``````m = a * (b / h)
``````

As h divides both a and b, you should perform the division first (as above), to reduce the risk of overflow.

Now all you need is an algorithm for the HCF. There are many, some very efficient. See http://rhubbarb.wordpress.com/2009/04/08/hcf-without-division/ for example.

For the case of the LCM of many numbers rather than just two, note that e.g.

``````LCM(a,b,c) = LCM(LCM(a,b),c)
``````