Search code examples
pythonpython-3.xlcm

How to find lcm of two numbers efficiently (With out using any module like `np.lcm`)?

I get this from the internet but it takes about 1 minute for the large numbers.

import time

def lcm(x,y):
    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

a = time.time()
num1 = 50342
num2 = 10000
print(f"Lcm of {num1} and {num2} is {lcm(num1,num2)}")

print("Time taken:", time.time() - a)

** OUTPUT **

Lcm of 50342 and 10000 is 251710000
Time taken: 39.7167

Is there a way to change this function and get the same result Fastly,

Note: Without using any module like np.lcm

Solution

  • i have a try on this,have a check plz

    def hcf(a,b):

    if a == 0:

        return b

    return hcf(b % a, a)
 

def lcm(a,b):

    return a * b / hcf(a,b)
 

a = 15

b = 30

print('LCM of', a, 'and', b, 'is', lcm(a, b))