提问者:小点点

最快和最紧凑的方法得到最小的数,可以被从1到n的数整除


我试着去找一个能被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


共3个答案

匿名用户

这里有一个非常快速的解决方案:

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)