Python 中的 Project Euler 5 - 如何优化我的解决方案? [英] Project Euler 5 in Python - How can I optimize my solution?

问题描述

我最近一直在研究 Python 中的 Project Euler 问题.我对 Python 相当陌生，作为一名程序员，我仍然有些陌生.

I've recently been working on Project Euler problems in Python. I am fairly new to Python, and still somewhat new as a programmer.

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

In any case, I've ran into a speed-related issue coding a solution for problem #5. The problem is,

2520 是可以被 1 到 10 的每一个数整除而没有余数的最小数.能被 1 到 20 的所有数整除的最小正数是多少?"

"2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?"

我已经检查了一些，但我无法找到任何与 Python 相关的问题.有一些完整的脚本，但如果可能的话，我想避免完整地查看其他人的代码，而是想改进我自己的代码.

I've checked around some, and I haven't been able to find anything on this problem pertaining to Python specifically. There were some completed scripts, but I want to avoid looking at other's code in full, if possible, instead wanting to improve my own.

我编写的代码以 2520 和范围 1 到 10 的示例成功运行，并且应该可以直接修改以处理该问题.但是，在运行它时，我没有得到答案.想必是个很高的数字，代码还不够快.打印当前正在检查的数字似乎支持这一点，达到几百万没有得到答复.

The code I have written runs successfully for the example of 2520 and the range 1 to 10, and should be directly modifiable to work with the question. However, upon running it, I do not get an answer. Presumably, it is a very high number, and the code is not fast enough. Printing the current number being checked seems to support this, reaching several million without getting an answer.

当前实现中的代码如下:

The code, in it's current implementation is as follows:

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 整除.(没查过那个，但似乎合理)

I have already made a couple changes which I think should help the speed. For one, for a number to be divisible by all numbers 1 to 20, it must be even, as only even numbers are divisible by 2. Hence, I can increment by 2 instead of 1. Also, although I didn't think of it myself, I found someone point out that a number divisible by 11 to 20 is divisible by 1 to 10. (Haven't checked that one, but it seems reasonable)

代码仍然不够快.我可以进行哪些优化，无论是编程的还是数学的，以使此代码运行得更快?

The code still, however is not fast enough. What optimisations, either programmatic, or mathematics, can I make to make this code run faster?

预先感谢任何可以提供帮助的人.

Thanks in advance to any who can help.

推荐答案

接受 Michael Mior 的建议和 poke，我写了一个解决方案.我尝试使用一些技巧使其快速.

Taking the advice of Michael Mior and poke, I wrote a solution. I tried to use a few tricks to make it fast.

由于我们需要测试的数字列表相对较短，因此我们可以预先构建数字列表，而不是重复调用 xrange() 或 range().

Since we need a relatively short list of numbers tested, then we can pre-build the list of numbers rather than repeatedly calling xrange() or range().

此外，虽然将数字 [1, 2, 3, ..., 20] 放在列表中是可行的，但我们可以稍微思考一下，然后将数字拉出来:

Also, while it would work to just put the numbers [1, 2, 3, ..., 20] in the list, we can think a little bit, and pull numbers out:

只需取出 1.每个整数都可以被 1 整除.

Just take the 1 out. Every integer is evenly divisible by 1.

如果我们保留 20 in，就没有必要保留 2 in.任何可以被 20 整除的整数都可以被 2 整除(但反过来可能不是真的).所以我们留下 20，去掉 2、4 和 5.留下 19，因为它是质数.留下 18，但现在我们可以去掉 3 和 6.如果重复这个过程，你会得到一个更短的数字列表来尝试.

If we leave the 20 in, there is no need to leave the 2 in. Any integer evenly divisible by 20 is evenly divisible by 2 (but the reverse might not be true). So we leave the 20 and take out the 2, the 4, and the 5. Leave the 19, as it's prime. Leave the 18, but now we can take out the 3 and the 6. If you repeat this process, you wind up with a much shorter list of numbers to try.

我们从 20 步开始，步数为 20，正如 Michael Mior 所建议的那样.正如 poke 建议的那样，我们在 all() 中使用了一个生成器表达式.

We start at 20 and step numbers by 20, as Michael Mior suggested. We use a generator expression inside of all(), as poke suggested.

我使用了带有 xrange() 的 for 循环而不是 while 循环；我认为这会稍微快一些.

Instead of a while loop, I used a for loop with xrange(); I think this is slightly faster.

结果:

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 秒内找到答案.

On my computer, this finds an answer in under nine seconds.

而且，如果我们听取 David Zaslavsky 的建议，我们就会意识到我们可以从 2520 开始循环，然后逐步到 2520.如果我这样做了，那么在我的计算机上，我会在大约十分之一秒内得到正确的答案.

And, if we take advice from David Zaslavsky, we realize we can start the loop at 2520, and step by 2520. If I do that, then on my computer I get the correct answer in about a tenth of a second.

我让 find_solution() 接受一个参数.尝试调用 find_solution(2520).

I made find_solution() take an argument. Try calling find_solution(2520).

这篇关于Python 中的 Project Euler 5 - 如何优化我的解决方案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！