How to get GCD and LCM of a range of numbers efficiently?
-
15-04-2021 - |
题
I currently use this code to find gcd and 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
But what if I want to do this for a list of numbers e.g. [4,5,7,1,5,7,10,1,16,24] etc? Am I constrained to loops?
其他提示
from fractions import gcd
def lcm(a, b):
return (a * b) // gcd(a, b)
You could use a recursive technique:
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a%b)
Store all your GCD values in a hash map. So, when it does the recursive step, it first accesses the hash map to see if the GCD of the smaller numbers has already been computed, which will save a lot of time if you were doing this for a large range of inputs.
不隶属于 StackOverflow