如何不使用np.lcm等模块高效快速计算两个数的最小公倍数

原暴力枚举实现的时间复杂度为O(LCM(x,y))，计算耗时随结果值增大线性增长，大数值场景下效率极低。

核心优化原理 #

利用数论中的固有公式推导结果，完全跳过枚举过程：

两个正整数的最小公倍数与最大公约数（GCD）满足恒等式：LCM(x,y) = x * y // GCD(x,y)

计算最大公约数采用欧几里得（辗转相除）算法，时间复杂度仅为O(log(min(x,y)))，对任意大的整数都能极速完成计算。

优化后完整代码 #

import time

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

def lcm(x, y):
    if x == 0 or y == 0:
        return 0
    return x * y // gcd(x, y)

if __name__ == "__main__":
    start = time.time()
    num1 = 50342
    num2 = 10000
    print(f"Lcm of {num1} and {num2} is {lcm(num1, num2)}")
    print("Time taken:", time.time() - start)

运行结果对比 #

相同测试参数下的输出：

Lcm of 50342 and 10000 is 251710000
Time taken: 9.5367431640625e-06

计算耗时从原实现的近40秒压缩到10微秒以内，性能提升超过400万倍，即使是十亿级以上的大整数计算，耗时也不会超过1毫秒。
实现注意点：最终计算时使用整数整除//而非浮点数除法/，避免大数值场景下出现浮点数精度丢失问题。

内容的提问来源于stack exchange，提问作者Sarim09