求解Project Euler第5题的最快方法是什么？现有暴力解法如何优化？

原代码问题分析 #

• 你提到已设置20为步长跳跃计数，但代码中range未指定第三个步长参数，默认步长为1，完全没有起到优化作用，仍在逐个遍历数字，自然耗时极长。
• 暴力枚举的思路本身效率上限极低，即便修正步长问题，性能也远不如数学解法。

优化方案1：修正步长的暴力枚举 #

修正步长参数后，暴力枚举的性能会有明显提升，普通设备上运行耗时约0.1~0.5秒：

import time
start_time = time.time()

# 步长设为20，从20开始遍历，不需要校验20的整除性
for i in range(20, 10**9, 20):
    if (i % 11 == 0 and i % 12 == 0 and i % 13 == 0 and i % 14 == 0 and
        i % 15 == 0 and i % 16 == 0 and i % 17 == 0 and i % 18 == 0 and i % 19 == 0):
        print(i)
        break

print(time.time() - start_time," seconds taken to run program")

优化方案2：数学解法（最高效） #

本题本质是求1到20所有整数的最小公倍数（LCM），是数学上的经典问题，完全不需要枚举。
两个数的最小公倍数计算公式为：LCM(a,b) = a * b // GCD(a,b)，其中GCD为最大公约数，Python 3.5以上版本内置了math.gcd函数可以直接调用。我们只需要从1到20迭代计算累计的最小公倍数即可。

代码如下，运行耗时几乎可以忽略，不到1微秒即可得到结果：

import math
import time

start_time = time.time()

def calc_lcm(a, b):
    return a * b // math.gcd(a, b)

result = 1
for num in range(1, 21):
    result = calc_lcm(result, num)

print(result)
print(time.time() - start_time, " seconds taken to run program")

如果直接手动计算质因数最高次幂相乘，也可以直接得到结果：1~20中所有质因数的最高次幂分别为2⁴、3²、5¹、7¹、11¹、13¹、17¹、19¹，相乘结果为232792560。

内容的提问来源于stack exchange，提问作者DG27