Least Common Multiple of given numbers

Question

Possible Duplicates:
what is the most efficient way to calculate the least common multiple of two integers
Least common multiple for 3 or more numbers

Whats the simple logic for calculating LCM of given numbers?

Answer 1

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

Answer 2

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.

Answer 3

There are several algorithms described on the Wikipedia page for LCM.

Answer 4

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)

Answer 5

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..)

Answer 6

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).

Answer 7

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)

See http://en.wikipedia.org/wiki/Least_common_multiple and http://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml for example.