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

Issue

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

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 us a relationship b\w 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
            break
    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 taken:", time.time() - a)

OUTPUT

Lcm of 50342 and 10000 is 251710000
Time taken: 0.00531005859375

I hope someone finds it helpful 😊.

Answered By - Sharim Iqbal