CODEWITHSUNDEEP
pythonrecursionlcm
ComputerGuy22
ComputerGuy22

Reputation: 41

LCM using recursive?

Here is my code: 

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

print lcm(5,3)

This is what I could manage so far, any idea on how to find the LCM (least common multiple) of two numbers using recursive and one function?

Upvotes: 2

Views: 13794

Answers (6)

tsh
tsh

Reputation: 4738

We have lcm(a, b) * gcd(a, b) = a * b. So we can write the following equation:

lcm(a, b) = a; if a % b == 0

lcm(a, b) ; if a % b != 0
= a * b / gcd(a, b)
= a * b / gcd(b, a % b)
= a * b / (b * (a % b) / lcm(b, a % b))
= a / (a % b) * lcm(b, a % b)

And translate to Python, we have:

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

Upvotes: 3

Saverio Guzzo
Saverio Guzzo

Reputation: 11

Using the mathematical relationship that the product of two numbers is equal to the product of the Greatest Common Divisor and the Least Common Multiplier of those two numbers: 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))

The first function is recursive and it's used to find the Greatest Common Divisor, it has cost O(log(n)).

Upvotes: 1

sameer_nubia
sameer_nubia

Reputation: 811

I created my own easy programme.

def lcm(greater,a,b):
# while(True):
    if (greater % a == 0 and greater % b == 0):
        lcm1 = greater
        return lcm1
    else:

        lcm1=lcm(greater + 1,a,b)
        return lcm1
a=int(input(" Enter 1st number :"))
b=int(input(" Enter 2nd number :"))
if(a>b):
  greater=a
else:
  greater=b

print(lcm(greater,a,b))

Upvotes: 0

Arnav Das
Arnav Das

Reputation: 301

As stated in the other answers here lcm = a*b / gcd(a, b)but then you will need to define another function gcd(a, b) for it.

Since you needed only 1 function with recursion, maybe this piece of code will do.

N.B. : This function has one extra parameter c which should be always passed as 1 while calling it outside the function only : 

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

Upvotes: 1

alksdjg
alksdjg

Reputation: 1149

Edit: I didn't read the recursive / one function bit in your question cause I'm dumb. Incorporated now.

The lcm isn't a * b / lcm(a, b), it's a * b / gcd(a, b) (greatest common divisor).

So the cleanest way to do this is:

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

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

If you are limited to recursion only (e.g. for an exam) then this doesn't have to be efficient, so you might as well just recursively count up until you find the lowest number that both x and y divide into:

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

That just increases counter until counter%x == 0 and counter%y == 0 is true, which is the LCM. Don't try it on large numbers though, you'll just get a stack overflow.

Upvotes: 1

Patrick Bassut
Patrick Bassut

Reputation: 3338

This should do:

# 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))

Upvotes: 0

Related Questions