0 
def getLCM(a, b):
    c, d = max(a, b), min(a, b)
    while c != d:
        temp = c - d
        c, d = max(temp, d), min(temp, d)

    return a * b // c


def nlcm(num):
    temp = 1
    while len(num) != 0:
        temp = getLCM(temp, num[-1])
        num.pop()
    return temp

print(nlcm([2,6,8,14,5]));

我需要“快速”回答这个问题。在测试用例中，我的代码很慢。

4

2 回答 2

2

Python中已有gcd实现，LCM 可以用 来定义gcd，所以你最好避免重新发明轮子。具体来说：

gcd(a, b) x lcm(a, b) = axb

在 Python 3.5 及更高版本中，模块gcd上有一个加速功能math，因此lcm可以简化为：

from math import gcd

def getLCM(a, b):
    return a * b // gcd(a, b)

在较旧的 Python 上，它没有加速，但fractions.gcd为您提供了一个不错的实现，因此您可以使用它，或者在gcd您运行的任何版本上使用最好的，嵌套导入尝试有效：

try:
    from math import gcd
except ImportError:
    from fractions import gcd

您的nlcm循环也可以简化：您不需要手动进行破坏性迭代，只需循环：

def nlcm(num):
    temp = 1
    for x in num:
        temp = getLCM(temp, x)
    return temp

或者，如果您想变得更聪明，请使用reduce(functools.reduce在 Python 3.x 上)，因为它完全符合简化循环已经在做的事情：

from functools import reduce

def nlcm(nums):
    return reduce(getLCM, nums, 1)
于 2017-10-27T01:22:05.420 回答
0

假设“长时间执行”不在您提供的示例中，而是在更大的输入中，您可以添加记忆并创建getLCM()计算时间，以防再次使用相同的数字调用它：

hash = dict() # we'll save here the calculated results

def getLCM(a, b):
    global hash
    if (a, b) in hash:  # if it was already calculated
        return hash[(a, b)]  # use the cached result
    c, d = max(a, b), min(a, b)
    while c != d:
        temp = c - d
        c, d = max(temp, d), min(temp, d)

    hash[(a, b)] = a * b // c. # cash the result
    return a * b // c
于 2017-10-27T01:24:12.287 回答