我最近在用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整除。因此,我可以将递增量从1改为2。此外,虽然我没有想到这个点子,但我发现有人指出,一个可以被11到20整除的数字也可以被1到10整除。(我还没有检查过,但这似乎是合理的)
然而,代码仍然不够快。有哪些优化措施,无论是程序方面还是数学方面,可以让这个代码运行得更快呢?
提前感谢任何能够帮助我的人。
232792560 = 2*2*2*2*3*3*5*7*11*13*17*19
。但是,要看问题类型来确定手动数学是否足够有效,或者一个简单的程序能否更快地(或更高效地)解决它。 - poke2*2*2*2*3*3*5*7*11*13*17*19
相乘只需要0.1微秒 :-P - David Z