# Least Common Multiple of an arbitrary number of positive integers

1. Jan 23, 2014

### Jamin2112

I need an algorithm for LCM(k1, k2, ..., kn).

Here's what I was thinking:

• any number ki that divides evenly into another number kj, set ki = 1
• return k1*k2*...*kn

I'm having trouble implementing it, though.

Code (Text):

int LCM(int* numsPtr, int size) {
// assume size > 1 and that array only contains non-negative numbers
std::vector<int> numsVec(numsPtr, numsPtr + size);
std::sort(numsVec.begin(), numsVec.begin() + size);
for (int k = 0; k < size - 1; ++k) {
for (int j = k; j < size; ++j) {
if (numsVec[j] % numsVec[k] == 0) {
numsVec[k] = 1;
break;
}
}
}
int product = 1;
for (int k = 0; k < size; ++k)
product *= numsVec[k];
return product;
}

Last edited: Jan 23, 2014
2. Jan 25, 2014

### Bill Simpson

What if you had k1=2*3, k2=2*5, k3=2*7? None evenly divides the other, but the LCM isn't k1*k2*k3, is it?

3. Jan 25, 2014

### AlephZero

The naive way is to factorize all the numbers.

A less naive way is to find their greatest common divisors. Some guy called Euclid found a neat way to do that.