3个或更多数字的最小公倍数

Question

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

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

到目前为止,这就是我做到的

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

使用gcd是计算数字的最大公约数的函数.使用欧几里得算法

但我无法弄清楚如何计算3个或更多数字.

Answer 1

您可以通过迭代计算两个数字的LCM来计算两个以上数字的LCM,即

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

Answer 2

在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)

Answer 3

这是一个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));
    }
}

Answer 4

我会选择这个(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);
}

只是一些澄清,因为乍一看它没有接缝这么清楚这个代码在做什么:

Aggregate是一个Linq扩展方法,所以你不能忘记使用System.Linq添加到你的引用.

Aggregate获取累积函数,因此我们可以在IEnumerable上使用属性lcm(a,b,c)= lcm(a,lcm(b,c)).更多关于聚合

GCD计算使用欧几里德算法.

lcm计算使用Abs(a*b)/ gcd(a,b),参考最大公约数的减少.

希望这可以帮助,

Answer 5

我只是在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中找到它!今天为我学习了很多:D

Answer 6

一些不需要gcd函数的Python代码:

from sys import argv 

def lcm(x,y):
    tmp=x
    while (tmp%y)!=0:
        tmp+=x
    return tmp

def lcmm(*args):
    return reduce(lcm,args)

args=map(int,argv[1:])
print lcmm(*args)

这是它在终端中的样子:

$ python lcm.py 10 15 17
510

Answer 7

这是一个Python单行(不计入导入),用于返回从1到20的整数的LCM:

Python 3.5+导入:

from functools import reduce
from math import gcd

Python 2.7导入:

from fractions import gcd

共同逻辑:

lcm = reduce(lambda x,y: x*y//gcd(x, y), range(1, 21))

在Python 2和Python 3中,运算符优先级规则规定*和//运算符具有相同的优先级,因此它们从左到右应用.因此,x*y//z手段(x*y)//z而不是x*(y//z).这两者通常产生不同的结果.这对于浮动分割来说并不重要,但它确实适用于地板分割.

Answer 8

这是在Swift 中。

// Euclid's algorithm for finding the greatest common divisor
func gcd(_ a: Int, _ b: Int) -> Int {
  let r = a % b
  if r != 0 {
    return gcd(b, r)
  } else {
    return b
  }
}

// Returns the least common multiple of two numbers.
func lcm(_ m: Int, _ n: Int) -> Int {
  return m / gcd(m, n) * n
}

// Returns the least common multiple of multiple numbers.
func lcmm(_ numbers: [Int]) -> Int {
  return numbers.reduce(1) { lcm($0, $1) }
}