Ускорение нахождения НОК двух чисел

Question

Я написал код для нахождения НОК заданных чисел, но он не вписывается в рамки времени. Подскажите пожалуйста как его ускорить.

b,n=map(int,input().split())
m=max(b,n)
while True:
    if m%b==0 and m%n==0:
        print(m)
        break
    else:
        m+=1

Время на работу программы 5 сек.

Answer 1

Нашел интересный пример в интернете. Как сказано на вики:

вики

import math
n = 14
m = 21

print((n * m) // math.gcd(n , m)) # gcd - greatest common devisor

gcd() появился только в Python версии 3.5

Answer 2

После долгой, неплодотворной дискуссии - вот вам решение с нуля.

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a
def mcd(n,m):
    return (n/gcd(n,m))*m  
print(int(mcd(n,m)))

При

n=14
m=21

ответ:

При

n=147
m=214

ответ 31458

При

n=14783678656
m=21456735976

ответ

39651186209477312512

Время работы - моментально. Проверяйте.

P.S. math.gcd() реализовано в стандартной библиотеке начиная с версии Python 3.5

Answer 3

В Python 3.9 добавлена функция для нахождения НОК:

import math

print(math.lcm(14, 21))

Также можно воспользоваться numpy:

import numpy as np

print(np.lcm(14, 21))