Least common multiple for 3 or more numbers

Solution 1:

You can compute the LCM of more than two numbers by iteratively computing the LCM of two numbers, i.e.

lcm(a,b,c) = lcm(a,lcm(b,c))

Solution 2:

In Python (modified primes.py):

def gcd(a, b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:      
        a, b = b, a % b
    return a

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)

def lcmm(*args):
    """Return lcm of args."""   
    return reduce(lcm, args)

Usage:

>>> lcmm(100, 23, 98)
112700
>>> lcmm(*range(1, 20))
232792560

reduce() works something like that:

>>> f = lambda a,b: "f(%s,%s)" % (a,b)
>>> print reduce(f, "abcd")
f(f(f(a,b),c),d)

Solution 3:

Here's an ECMA-style implementation:

function gcd(a, b){
    // Euclidean algorithm
    while (b != 0){
        var temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function lcm(a, b){
    return (a * b / gcd(a, b));
}

function lcmm(args){
    // Recursively iterate through pairs of arguments
    // i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))

    if(args.length == 2){
        return lcm(args[0], args[1]);
    } else {
        var arg0 = args[0];
        args.shift();
        return lcm(arg0, lcmm(args));
    }
}

Solution 4:

I would go with this one (C#):

static long LCM(long[] numbers)
{
    return numbers.Aggregate(lcm);
}
static long lcm(long a, long b)
{
    return Math.Abs(a * b) / GCD(a, b);
}
static long GCD(long a, long b)
{
    return b == 0 ? a : GCD(b, a % b);
}

Just some clarifications, because at first glance it doesn't seams so clear what this code is doing:

Aggregate is a Linq Extension method, so you cant forget to add using System.Linq to your references.

Aggregate gets an accumulating function so we can make use of the property lcm(a,b,c) = lcm(a,lcm(b,c)) over an IEnumerable. More on Aggregate

GCD calculation makes use of the Euclidean algorithm.

lcm calculation uses Abs(a*b)/gcd(a,b) , refer to Reduction by the greatest common divisor.

Hope this helps,

Solution 5:

I just figured this out in Haskell:

lcm' :: Integral a => a -> a -> a
lcm' a b = a`div`(gcd a b) * b
lcm :: Integral a => [a] -> a
lcm (n:ns) = foldr lcm' n ns

I even took the time to write my own gcd function, only to find it in Prelude! Lots of learning for me today :D