如何有效地获得一系列数字范围的GCD和LCM?
-
26-10-2019 - |
题
我目前使用此代码查找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]等?我被限制在循环吗?
其他提示
from fractions import gcd
def lcm(a, b):
return (a * b) // gcd(a, b)
您可以使用递归技术:
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a%b)
将所有GCD值存储在哈希地图中。因此,当它执行递归步骤时,它首先访问Hash地图,以查看是否已经计算出较小数字的GCD,如果您要为大量输入进行此操作,这将节省大量时间。
不隶属于 StackOverflow