Least Common Multiple of given numbers [duplicate]

This question already has answers here: 开发者_如何学编程 Closed 12 years ago.

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?

---

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)

---

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.

---

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

---

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

---

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

---

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.

---

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