python - 最快，最紧凑的方法来获得最小的数字，该数字可被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对于将关联操作应用于互操作性很有用。我们可以结合这些想法(以及马克·迪金森和埃里克·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)

在IPython中，一些快速的 %timeit结果:

%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。