Python实现Project Euler第5题 - 如何优化我的解决方案？
我最近在用Python做Project 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整除。（我还没验证这一点，但听起来合理）
不过，代码的速度仍然不够快。我可以做哪些程序上的优化或者数学上的改进来让这段代码运行得更快呢？
提前感谢任何能提供帮助的人。
21 个回答
因为你的答案必须是20的倍数，所以你可以从20开始，每次加20，而不是加2。一般来说，你可以从rangemax开始，每次加rangemax。这样做可以大大减少div_check被调用的次数。
我之前的回答加快了问题中原始计算的速度。
这里有另一个不同的方法来解决这个问题：只需找到每个数字的所有质因数，然后把它们相乘，就能直接得到答案。换句话说，这个方法自动化了poke在评论中推荐的过程。
这个方法在几毫秒内就能完成。我觉得没有比这更快的方法了。
我在谷歌上搜索了“用Python找质因数”，找到了这个链接：
http://www.stealthcopter.com/blog/2009/11/python-factors-of-a-number/
从那里我找到了一个链接，里面有个叫factor.py的文件（由Mike Hansen写的），里面有一些有用的函数：
https://gist.github.com/weakish/986782#file-factor-py
他的函数没有完全满足我的需求，所以我写了一个新的函数，但用了他的pull_prime_factors()来处理复杂的部分。结果是find_prime_factors()，它返回一个元组的列表：一个质数和一个计数。例如，find_prime_factors(400)返回[(2,4), (5,2)]，因为400的质因数是：(2*2*2*2)*(5*5)
然后我用一个简单的defaultdict()来记录到目前为止我们见过的每个质因数的数量。
最后，一个循环把所有的数相乘。
from collections import defaultdict
from factor import pull_off_factors
pf = defaultdict(int)
_primes = [2,3,5,7,11,13,17,19,23,29]
def find_prime_factors(n):
lst = []
for p in _primes:
n = pull_off_factors(n, p, lst)
return lst
def find_solution(low, high):
for num in xrange(low, high+1):
lst = find_prime_factors(num)
for n, count in lst:
pf[n] = max(pf[n], count)
print "prime factors:", pf
solution = 1
for n, count in pf.items():
solution *= n**count
return solution
if __name__ == '__main__':
solution = find_solution(1, 20)
print "answer:", solution
补充：哇，我刚刚看了@J.F. Sebastian对一个相关问题的回答。他的回答实际上和上面的代码做的事情是一样的，只是更简单优雅。而且它的速度确实比上面的代码快。
我会保留上面的内容，因为我觉得这些函数在Project Euler中可能还有其他用途。但这是J.F. Sebastian的解决方案：
def gcd(a, b):
"""Return greatest common divisor using Euclid's Algorithm."""
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""Return lowest common multiple."""
return a * b // gcd(a, b)
def lcmm(*args):
"""Return lcm of args."""
return reduce(lcm, args)
def lcm_seq(seq):
"""Return lcm of sequence."""
return reduce(lcm, seq)
solution = lcm_seq(xrange(1,21))
print "lcm_seq():", solution
我添加了lcm_seq()，但你也可以调用：
lcmm(*range(1, 21))
根据Michael Mior和poke的建议，我写了一个解决方案。我尝试用一些小技巧来提高速度。
因为我们需要测试的数字列表相对较短，所以我们可以提前准备好这个数字列表，而不是反复调用xrange()或range()。
另外，虽然直接把数字[1, 2, 3, ..., 20]放在列表里也能工作，但我们可以稍微动动脑筋，把一些数字去掉：
首先，把1去掉。每个整数都能被1整除。
如果我们保留20，就没必要保留2了。任何能被20整除的整数也能被2整除（但反过来就不一定）。所以我们保留20，去掉2、4和5。19是个质数，留着它。18也留着，但我们可以去掉3和6。如果你重复这个过程，最终会得到一个更短的数字列表。
我们从20开始，每次加20，正如Michael Mior所建议的那样。我们在all()里面使用了生成器表达式，正如poke所建议的。
我用for循环代替了while循环，并使用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
在我的电脑上，这个方法在九秒内找到了答案。
编辑：如果我们听从David Zaslavsky的建议，可以从2520开始循环，每次加2520。如果这样做的话，在我的电脑上大约只需十分之一秒就能得到正确答案。
我让find_solution()接受一个参数。试试调用find_solution(2520)。