python - 编程新手，这段 Python 代码的计算时间似乎很长

Question

所以我是一名新程序员，在大学学习CS。我是 Python 的新手，一直在解决项目欧拉难题，我想知道为什么我的数字 5 需要这么长时间才能计算!看起来像 287 秒。我得到了正确答案，但计算时间很长。谁能向我解释这是为什么，以及我如何才能更好地优化它以使其运行得更快？

对于不熟悉欧拉计划的人来说，这个问题是要我找到第一个可被 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

您的程序一个一个地遍历每个可能的数字，直到找到解决方案。这是蛮力解决方案。欧拉计划问题旨在挫败蛮力方法。改进直接方法需要聪明才智。有时这意味着完善您的答案。有时这意味着完全重新考虑它。

优化

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

x = x + 2

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

x = x + 6

它必须能被 5 整除，对吗？哎呀，让我们一次数 30。现在我们开始做饭了!

x = x + 30

你可以一直按照这个思路，把增量做的越来越大。但这将是退后一步的好时机。让我们重新考虑整个方法。我们需要迭代吗？这一切将走向何方？

反射(reflection)

如果我们将 1×2×3×4×5...×19×20 相乘，我们将得到一个可以被 1 整除到 20 的数字。但它不会是最小这样的数字。

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

突破是只乘以主要因素。我们不需要 6，因为我们已经有了 2 和 3。如果我们将两个 3 相乘，我们就不需要 9。

问题是，我们需要每个素因子的多少？有几个2？有几个3？答案:我们需要足够的数字来覆盖最多 20 个数字。我们最多需要四个 2，因为 16 = 2⁴。我们不需要五个，因为没有数字包含五个 2。我们需要两个 3 来处理 9 和 18。我们只需要 5、7、11、13、17 和 19 中的每一个——没有一个数字超过一次。

这样，我们就可以手算答案了。我们甚至不需要程序!

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