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

Question

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

Answer 1

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

Answer 2

Note: GCF, GCD, and HCF are the same. All names are used to represent a similar method of finding the highest or greatest common factor/divisor.

Yes, there's a fast way to do that.

There is a relationship between LCM and HCF.

a x b = HCF(a, b) x LCM(a, b)
Here, LCM(a, b) = HCF(a, b) / (a x b)

Finding HCF is an easy and fast way, therefore, using this relation you can get the same result easily and fastly.

import time

def hcf(x, y):
    smaller = min((x, y))
    for i in range(1, smaller + 1)[::-1]: # Here I am reversing the range Now it is going from larger to the smaller number because the HCF Stand For the Highest Common Factor.
        if((x % i == 0) and (y % i == 0)):
            hcf = i
            return hcf


def lcm(x,y):
    return round((x*y)/hcf(x,y))

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

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

OUTPUT

Lcm of 50342 and 10000 is 251710000
Time took: 0.00531005859375

I hope someone finds it helpful .

Answer 3

You can try this way also.

num1 = 12
num2 = 14
for i in range(max(num1, num2), 1 + (num1 * num2)):
    if i % num1 == i % num2 == 0:
        lcm = i
        break
print("LCM of", num1, "and", num2, "is", lcm)