Python中的Euler 5项目-如何优化解决方案？

Question

我最近一直在研究Python中的Euler项目问题​​。我对Python相当陌生，但作为一名程序员还是有点陌生​​。

无论如何，我遇到了与速度相关的问题，为问题5编写了解决方案。问题是，

“ 2520是可以除以1到10的每个数字而没有任何余数的最小数字。什么是可以被1到20的所有数字平均除的最小正数？

我已经检查了一些，但还没有找到关于此问题的任何有关Python的信息。有一些完整的脚本，但是我想避免看完整的他人代码，如果可能的话，而是想改进自己的代码。

我编写的代码可以成功运行2520示例，范围为1到10，并且可以直接修改以解决问题。但是，运行它时，我没有得到答案。据推测，这是一个非常高的数字，并且代码不够快。打印当前正在检查的数字似乎可以支持这一点，达到数百万而没有得到答案。

当前实现中的代码如下：

rangemax = 20
def div_check(n):
    for i in xrange(11,rangemax+1):
        if n % i == 0:
            continue
        else:
            return False
    return True

if __name__ == '__main__':
   num = 2
   while not div_check(num):
       print num
       num += 2
   print num

我已经进行了一些更改，我认为这些更改应该有助于提高速度。对于一个，要使一个数字可以被1到20的所有数整除，它必须是偶数，因为只有偶数可以被2整除。因此，我可以加2而不是1。就我自己而言，我发现有人指出一个可以被11到20整除的数字可以被1到10整除。（没有检查那个，但是看起来很合理）

代码仍然，但是还不够快。我可以对程序或数学进行哪些优化，以使此代码运行更快？

在此先感谢任何可以提供帮助的人。

Answer 1

在迈克尔·迈尔（Michael Mior）的建议下，我and了oke。我尝试使用一些技巧来使其快速。

由于我们需要一个相对较短的数字列表，因此我们可以预先构建数字列表，而不用反复调用xrange()或range()。

另外，虽然只将数字[1, 2, 3, ..., 20]放在列表中是可行的，但我们可以考虑一下，然后取出数字：

只需取出1。每个整数均可以被1整除。

如果我们将20英寸留在，则无需保留2英寸。任何被20整除的整数都可以被2整除（但反之可能不成立）。因此，我们留下20，取出2、4和5。保留19，因为它是素数。保留18，但现在我们可以取出3和6。如果重复此过程，最后会出现一个简短得多的数字列表。

正如迈克尔·迈尔（Michael Mior）所建议的，我们从20开始，然后以20为步长。all()正如戳建议的那样，我们在中使用了生成器表达式。

取而代之的是中while环，我用了一个for环带xrange(); 我认为这稍微快一点。

结果：

check_list = [11, 13, 14, 16, 17, 18, 19, 20]

def find_solution(step):
    for num in xrange(step, 999999999, step):
        if all(num % n == 0 for n in check_list):
            return num
    return None

if __name__ == '__main__':
    solution = find_solution(20)
    if solution is None:
        print "No answer found"
    else:
        print "found an answer:", solution

在我的计算机上，这可以在9秒内找到答案。

编辑：而且，如果我们听取大卫·扎斯拉夫斯基（David
Zaslavsky）的建议，我们意识到我们可以在2520开始循环，然后在2520之前完成。如果我这样做，那么在我的计算机上，我会在十分之一秒内得到正确的答案。

我提出了find_solution()一个论点。尝试致电find_solution(2520)。