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

Question

我正在经历euler项目，和很多人一样，我被效率所困扰。我不介意尝试将时间从7毫秒缩短到6毫秒，但我确实关心必须等待半个小时才能完成循环。 问题是:

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 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()

如您所见，它循环遍历每个数字，直到max safe整数的sqrt（）。之所以使用sqrt()是因为我试图提高效率，但始终没有达到这一点。我让它运行了大约15分钟，大约达到了200万（这是变量multiples为2并递增1的时候）。然后，我尝试将multiple变量增加20（如上所示），在15分钟多一点的时间里，我得到了4500万。我在做euler项目时看到了答案，大约有2亿。我没有作弊，我只是确保我的程序有问题，并且没有跳过那个目标数字。我说，怎样才能在一分钟内得到答案呢。正如我所说，我不是一个效率怪胎，我只想在一分钟内看到结果

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

另外，我不想直接重写我的代码，因此这里或那里的一些示例代码和一些提示可能会很好。（因此我实际上学习并改进了我的编码。）

Answer 1

我不熟悉ProjectEuler，但这个问题实际上不是一个编程问题，而是一个数学问题。答案是2^4*3^2*5*7*11*13*17*19

如果你试着从1开始看每个数字，直到找到一个符合标准的数字，那么你解决问题的方法就错了

您的目标是计算lcm(1, 2, 3, 4, .... 20)，即least common multiple。对stackoverflow的一些搜索将向您展示如何计算数字列表的lcm。有趣的是，math.lcm将被添加到Python3.9中