project euler#5的代码不起作用

Question

euler 5项目的问题是： 2520是一个最小的数，它可以被1到10之间的每一个数除掉，而没有余数。 能被1到20的所有数整除的最小正数是多少？在

result=1
done=False
while not done:
    result+=1
    for x in range(2,21):
        if result%x!=0:
            break
        elif x==20:
            done=True
print(result)

但它运行的时间太长了。好吧，看来这个代码不起作用了。这个代码有什么问题？在

Answer 1

你要找的是数字1到20中的“最小公倍数”，或LCM。这是这些数的多组素数因子的并集。例如，12和15的LCM是多集{2，2，3}和{3，5}的并集，即{2，2，3，5}，或60。在

如果有一个GCD函数（“最大公约数”），那么可以利用LCM（x，y）=x*y//GCD（x，y）这一事实。然后，您可以通过从1开始依次添加每个数字的唯一因子来累积LCM。在

如果您使用的是python3，那么可以从math.gcd获得GCD。例如，以下将给出1到10的答案：

import math
r = 1
for i in range(2, 11):
    r = r * i // math.gcd(r, i)

print(r)

这将按预期给出2520。对于1到20，只需：

^{pr2}$

这给出232792560。在

这两种计算基本上都是瞬时的。在

更新：实际上，您可以通过将循环体替换为：

    r *= i // math.gcd(r, i)

这是因为i是math.gcd(r, i)的倍数。通过先除后乘，计算中涉及的数字要小一些。在

Answer 2

因为它必须被20除，所以你只能检查20的倍数，这样你就可以检查更少的数字。在

如果数字被20除，那么它必须被2，10（20=2*10），4，5（20=4*5），这样你就不必检查2，4，5，10。同样的方法你可以消除其他数字。在

最后我得到了列表20，19，18，17，16，15，14，13，11

import time

start = time.time()

result = 0
done = False

while not done:
    result += 20
    for x in [20, 19, 18, 17, 16, 15, 14, 13, 11]:
        if result % x != 0:
            break
    else:
       done = True

end = time.time()

print('result:', result)
print('time in seconds:', end-start)

结果：

^{pr2}$