获得可被 1 到 n 的数字整除的最小数字的最快和最紧凑的方法

Question

我试图找到可以被 1 到 n 的数字整除的最小数字，现在我正在寻找有关进一步压缩/使我的解决方案更有效的方法的建议。如果也有 O(1) 解决方案，那就太酷了。

def get_smallest_number(n):
    """
    returns the smallest number that is divisible by numbers from 1 to n
    """
    divisors = range(1, n+1)
    check_divisible = lambda x: all([x % y == 0 for y in divisors])
    i = 1
    while True:
        if check_divisible(i):
            return i
        i += 1

Answer 1

在数学上，您正在计算 的最小公倍数1, 2, ..., n。lcm很容易从 导出gcd，并且lcm是一个关联操作。reduce可用于将关联操作应用于可交互对象。我们可以结合这些想法（以及 Mark Dickinson 和 Eric Postpischil 在评论中的改进）来获得一个非常快速的解决方案：

from math import gcd
from functools import reduce

def lcm(a,b):
    return a // gcd(a,b) * b

def get_smallest_number2(n):
    return reduce(lcm,range(1 + n//2,n+1),1)

%timeitIPython 中的一些快速结果：

%timeit get_smallest_number2(15)
2.07 µs ± 26.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit get_smallest_number(15)
443 ms ± 5.75 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

因为n = 15它因此快了 200,000 倍以上。您的函数很久以前就无法产生任何输出n = 100，但几乎立即get_smallest_number2(100)评估为69720375229712477164533808935312303556800。