对于 Project Euler #5，除了暴力之外，还有更有效的方法吗？

Question

我正在经历欧拉项目，和很多人一样，我陷入了效率的困境。我不介意尝试将时间从 7 毫秒减少到 6 毫秒，但我确实关心循环必须等待半个小时。问题是：

能被 1 到 20 中所有数字整除的最小正数是多少？

我认为我在 python 中有一个有效的解决方案，但效率非常低。

import sys

import math

def multiple():

    multiple = 20

    multiples = []

    while multiple < math.sqrt(sys.maxsize):

        div_flag = False

        max_flag = False

        for i in range(2, 21):

            if multiple % i == 0:

                div_flag = True

                if i == 20:

                    max_flag = True

                else:

                    max_flag = False

            if multiple % i != 0:

                div_flag = False

                break

        if max_flag == True:

            multiples.append(multiple)

            multiple = math.sqrt(sys.maxsize)

        multiple += 20

        print(multiple, "div_flag: " + str(div_flag), "max_flag: " + str(max_flag), str(multiples)) 

    # These prints are just there for debugging.

    print(multiples)

multiple()

正如您所看到的，它循环遍历每个数字，直到最大安全整数的 sqrt() 为止。原因是sqrt()因为我试图让它更有效率，但无论如何它从未达到这一点。我让它运行了大约 15 分钟，数量达到了 200 万左右（这是当变量multiples为 2 并增加 1 时的情况）。然后，我尝试增加multiple变量 20（如上所示），在 15 分钟多一点的时间里，我得到了 4500 万。我在做project euler的时候看了一下答案，大概是2亿左右。我没有作弊，我只是确保我的程序有问题，并且没有跳过那个目标数字。我说，怎样才能让我在一分钟之内得到答案。正如我所说，我不是一个效率狂，我只是想在一分钟内看到结果。

我对 python 相当陌生，所以我知道有一些非常明显的答案。

PS我不喜欢直接重写我的代码，所以也许这里和那里有一些示例代码，以及一些提示会很好。（所以我实际上学习并改进了我的编码。）

Answer 1

我不熟悉欧拉项目，但这个问题实际上并不是一个编程问题，而是一个数学问题。答案就是2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19。如果您尝试查看从 1 开始的每个数字，直到找到符合标准的数字，那么您就错误地解决了问题。您的目标是计算lcm(1, 2, 3, 4, .... 20)最小公倍数。stackoverflow 上的一些搜索将向您展示如何计算数字列表的 lcm。有趣的是，它将被添加到 Python 3.9 中。math.lcm