Least Common Multiple of an arbitrary number of positive integers

[Jamin2112]

I need an algorithm for LCM(k₁, k₂, ..., k_n).

Here's what I was thinking:

• any number k_i that divides evenly into another number k_j, set k_i = 1
• return k₁*k₂*...*k_n

I'm having trouble implementing it, though.

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;
}

 

[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?

 

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