Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Least Common Multiple of an arbitrary number of positive integers

  1. Jan 23, 2014 #1
    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. jcsd
  3. Jan 25, 2014 #2
    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?
     
  4. Jan 25, 2014 #3

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Least Common Multiple of an arbitrary number of positive integers
Loading...