python - 再帰を使用するLCM?

Question

これが私のコードです：

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

print lcm(5,3)

これは私がこれまでに管理できたもので、再帰関数と 1 つの関数を使用して 2 つの数値の LCM (最小公倍数) を見つける方法についてのアイデアはありますか?

Answer 1

編集：あなたの質問の再帰的/ 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 である true になるまでカウンターを増やすだけです。ただし、大きな数で試してはいけません。スタック オーバーフローが発生するだけです。

Answer 2

これは次のことを行う必要があります。

# Python Program to find the L.C.M. of two input number

# define a function
def lcm(x, y):
   """This function takes two
   integers and returns the L.C.M."""

   # choose the greater number
   if x > y:
       greater = x
   else:
       greater = y

   while True:
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1

   return lcm


# take input from the user
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

print("The L.C.M. of", num1,"and", num2,"is", lcm(num1, num2))