- #1
Jamin2112
- 986
- 12
I need an algorithm for LCM(k1, k2, ..., kn).
Here's what I was thinking:
I'm having trouble implementing it, though.
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:
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: