使用递归的LCM？

Question

下面是我的代码：

def lcm(a, b):
    if b == 0:
        return a
    return a * b / lcm(a, b)

print lcm(5,3)

到目前为止，这就是我所能做到的，你知道如何使用递归和一个函数来找到两个数字的最小公倍数( LCM )吗？

Answer 1

编辑：我没有读你问题中的递归/一函数位，因为我是哑巴。现已合并。

lcm不是a * b / lcm(a, b)，而是a * b / gcd(a, b) (最大公约数)。

因此，最干净的方法是：

def gcd(x, y):
    while y:      
        x, y = y, x % y
    return x

def lcm(x, y):
    return x * y / gcd(x, y)

如果你仅限于递归(例如，对于考试)，那么这不一定是有效的，所以你可以递归地向上计数，直到你找到x和y都划分成的最小数字：

def lcm(x, y, counter=1):
    if (counter%x == 0 and counter%y == 0):
        return counter
    return lcm(x, y, counter+1)

这只会增加计数器，直到counter%x == 0 and counter%y == 0为真，这就是LCM。不要在大数字上尝试它，你只会得到一个堆栈溢出。

Answer 2

正如在这里的其他答案中所述，lcm = a*b / gcd(a, b)，但是您将需要为它定义另一个函数gcd(a, b)。

因为你只需要一个带递归的函数，也许这段代码就行了。

注:此函数有一个额外的参数c，当仅在函数外部调用它时，应始终将其作为1传递：

def lcm(a, b, c):
d = c
m = min(a, b)
while m > 1 :
    if a%m == 0 and b%m == 0 :
        d*=m 
        return lcm(int(a/m), int(b/m), d)
    else:
        m-= 1
d*= a*b
return d

Answer 3

利用两个数的乘积等于这两个数的最大公约数和最小公约数的乘积的数学关系:A*B= GCD(A，B) * LCM(A，B)

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

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

第一个函数是递归的，它用于寻找最大的公约数，它的代价是O(log(n))。