Как эффективно получить 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 на карте хэш. Таким образом, когда он делает рекурсивный шаг, он сначала обращается к хеш -карте, чтобы увидеть, был ли GCD меньших чисел уже вычислен, что сэкономит много времени, если вы делаете это для большого диапазона входов.
Не связан с StackOverflow