如何有效地获得一系列数字的GCD和LCM？

我目前使用此代码找到最大公约数和最小公倍数如何有效地获得一系列数字的GCD和LCM？

def gcd(a, b): 
    while b != 0: 
     a, b = b, a%b 
    return a 

def lcm(a, b): 
    result = a*b/gcd(a,b) 
    return result

但是如果我要为号码列表做到这一点如[4,5,7,1,5,7,10,1,16,24]等？我受限于循环？在哈希表

def gcd(a, b): 
    if b == 0: 
     return a 
    else: 
     return gcd(b, a%b)

存储您所有的GCD值：

2012-01-10 John Smith

如果你已经计算出的值，您可以节省计算值在某种与第一次检查的有一个HashMap，如果你有你不需要重新计算它，否则，你将有至。 – lfxgroove 2012-01-10 16:18:47

@Anton。另外，将所有中间结果保存（缓存）到内存中，并在每次迭代中检查缓存。对于足够大的数目足够大的列表，这将更快。 – Martijn 2012-01-10 16:29:43

我知道如何使用memoization分类器;我怎么能在这里使用这些？ – 2012-01-10 16:31:48

正如Chris J提到的this SO问题提供了算法。这是Python版本的答案，它使用自2.6版以来已有的reduce内置模块和模块。

import fractions 

def gcd(*values): 
    return reduce(fractions.gcd, values)

2012-01-11 01:28:05

你可以使用一个递归技术。因此，当它执行递归步骤时，它首先访问哈希映射以查看是否已经计算出较小数字的GCD，如果您在大范围的输入中执行此操作，这将节省大量时间。

2012-01-10 17:08:02 HexTree

from fractions import gcd 
def lcm(a, b): 
    return (a * b) // gcd(a, b)

2015-07-23 21:53:25

回答