我试着去找一个能被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
这里有一个非常快速的解决方案:
from math import gcd
from functools import reduce
def lcm(a,b):
return a*b // gcd(a,b)
def get_smallest_number2(n):
return reduce(lcm,range(1,n+1),1)
IPython中的一些快速%timeIt结果:
%timeit get_smallest_number2(15)
3.16 µs ± 18.4 ns per loop (mean ± std. dev. of 7 runs, 100000 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，它的速度因此超过100,000倍。 您的函数在n=100之前很久就无法产生任何输出，但get_smallest_number2(100)的计算结果几乎立即为69720375229712477164533808935312303556800。
将时间缩短一半的一个方法是只检查偶数（我猜如果n是1，你可能仍然想检查1）。 在1以上，没有奇数可以被从1到n的数整除，因为2必须在那个范围内。 同样，你可以从n开始，而不是从1开始，因为小于n的数字都不能被n整除。 所有这些解都不会改变算法是O(n^2)的事实。 也许有办法改变这一点，但我没想到。
其思想是在每次迭代中添加最高分频器，并从高到低进行检查。 像这样的东西:
n = int(input("n = "))
result = 0
while True:
result += n
for i in range(n, 1, -1):
if result % i != 0:
break
else:
break
print(result)
