如何有效地獲得一系列數字的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

回答