如何计算多个数字的最小公倍数？

到目前为止，我只能在两个数字之间进行计算。但是不知道如何扩展它来计算3个或者更多的数字。

到目前为止，这就是我的做法

LCM = num1 * num2 /  gcd ( num1 , num2 )

使用gcd可以计算数字的最大公约数。使用欧几里得算法

但是我不知道如何计算3个或者更多数字。

解决方案

我们可以通过迭代计算两个数字的LCM来计算两个以上的LCM。

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

在Python中(修改了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)

用法：

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

reduce()的工作原理是这样的：

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

我只是在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

我什至花时间编写了自己的gcd函数，只是在Prelude中找到了它！今天对我来说是很多学习

这是ECMA样式的实现：

function gcd(a, b){
    // Euclidean algorithm
    var t;
    while (b != 0){
        t = b;
        b = a % b;
        a = t;
    }
    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));
    }
}