对于编程来说，对于Python-cod来说，计算时间似乎很长

Question

所以我是一个新的程序员，在大学里学计算机。我是Python新手，一直在解决projecteuler谜题，我想知道为什么我的数字5需要这么长时间来计算！看起来有287秒。我得到了正确的答案，但是计算时间很长。有人能解释一下为什么会这样吗？我怎样才能更好地优化它以更快地运行？在

对于不熟悉ProjectEuler的人来说，这个问题要求我找出第一个可以被1到20整除的正数。在

编辑：谢谢大家的帮助。我不知道如何评论评论，但你的建议很有帮助。谢谢！！在

import time
def main():
    time_start = time.clock()
    x=2
    while True:
        if divBy20(x)==True:
            print(x)
            break
        else:
            x=x+1

    time_elapsed = (time.clock() - time_start)
    print(time_elapsed)

def divBy20(a):
    for i in range(1,21):
        if a%i!=0:
            return False
    return True

main()

Answer 1

你的程序一个接一个地遍历每一个可能的数字，直到找到解决方案。这是暴力解决方案。Euler项目的问题旨在挫败暴力方法。改进直接法需要聪明。有时候这意味着你要完善你的答案。有时候，这意味着要彻底反思。在

精炼

这个问题就是一个很好的例子。你可以对你的算法进行一些渐进的改进。例如，你知道答案必须是偶数，那么为什么不跳过奇数呢？在

x = x + 2

事实上，它必须可以被3整除，所以我们甚至可以用6的倍数来计算。在

^{pr2}$

它必须能被5整除，对吗？见鬼，我们一次数到30。现在我们在做饭！在

x = x + 30

你可以继续遵循这个思路，让增量越来越大。但现在是退后的好时机。让我们重新考虑一下整个方法。我们需要迭代吗？这一切都往哪儿去了？在

重新思考

如果我们把1×2×3×4×5…×19×20相乘，我们就得到了一到二十可除的a数。但这并不是最小的数字。在

为什么？好吧，它太大的原因是数字之间的重叠。如果我们要乘以4，就不必乘以2。如果我们要乘以6，就不必乘以3。在

突破之处在于只增加素数因子。我们不需要6个，因为我们已经有2个和3个了。如果我们乘以两个3，就不需要9

问题是，我们需要多少个基本因子？多少个2？多少个3？答案是：我们需要足够的数据来覆盖最多20个数字。我们最多需要4个2，因为16=2⁴。我们不需要5个，因为没有一个号码里有5个2。我们需要两个3来处理9和18。我们只需要5，7，11，13，17，19中的每一个，没有一个号码可以超过一次。在

有了这些，我们就可以手工计算答案了。我们甚至不需要程序！在

2⁴ × 3² × 5 × 7 × 11 × 13 × 17 × 19 = 232,792,560