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?

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?

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

Alexandre C.
2010-07-09 16:42:29

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.

Mark Ransom
2010-07-09 16:43:24

+1
A:

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

Paul R
2010-07-09 16:43:24

+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)
```

Viele
2010-07-09 16:43:41

abs will work or not

anurag18294
2010-07-09 16:46:19
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.

Viele
2010-07-09 16:58:19
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..)

Jack
2010-07-09 16:45:23

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

.

Heath Hunnicutt
2010-07-09 16:46:47

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

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

Rhubbarb
2010-07-09 16:54:04