对于编程来说，对于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

Answer 2

您可以通过一些明显的方法来加快速度，例如：

• 从最小的可能数开始，（提示20以下的任何内容都不能被20整除，这将跳过18步）
• 步进2将跳过奇数但
• 你的数字必须能被你所有的因子除以你的最大除数（20这将减少你的工作95%）

• 埃茨。在

  但是一个更好的方法是考虑所有可能的解决方案都是部分或全部因素的乘积，因此您只需检查3-19个因素的可能乘积，保留那些满足要求的，然后返回最低值。您可以进一步删除高因子中存在的那些因子，例如2、4和5已经在20中，3在9中，等等。

Answer 3

Euler 5项目

考虑到主要因素：

1 = 1
2 = 2
3 = 3
4 = 2^2
5 = 5
6 = 2 * 3
7 = 7
8 = 2^3
9 = 3^3
10 = 2 * 5
11 = 11
12 = 2^2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2^4
17 = 17
18 = 2 * 3^2
19 = 19
20 = 2^2 * 5

那么这个问题真的是： 乘积（（a素数）**（此公因数的最大倍数），所有公因数）

^{pr2}$

顺便说一句，你似乎不是第一个落入暴力陷阱的人：Project Euler 5 in Python - How can I optimize my solution?

现在找出如何在代码中实现这一点。在