我想解决欧拉计划的第12个问题。我能在4分钟内计算出超过500个除数。我怎样才能更快?这是尝试
import time
def main():
memo={0:0,1:1}
i=2
n=200
while(1):
if len(getD(getT(i)))>n:
break
i+=1
print(getT(i))
#returns the nth triangle number
def getT(n):
if not n in memo:
memo[n]=n+getT(n-1)
return memo[n]
#returns the list of the divisors
def getD(n):
divisors=[n]
for i in xrange(1,int((n/2)+1)):
if (n/float(i))%1==0:
divisors.append(i)
return divisors
startTime=time.time()
main()
print(time.time()-startTime)
不需要数组来存储三角形数字。您可以使用单个int,因为您只检查一个值。另外,使用三角形数公式可能会有帮助:在这里可以找到第
n
个三角形数。getD
也只需要返回一个数字,因为您只需要查找500个除数,而不是除数的值。然而,真正的问题在于for循环中的
n/2
。通过检查因子对,可以使用sqrt(n)
。所以只检查到sqrt(n)
的值。如果你检查到n/2
,你会得到大量浪费的测试(以百万计)。因此,您需要执行以下操作(
n
是查找除数的整数,d
是可能的除数):n/d
没有余数。一些评论。
正如Quincunx所写,您只需要检查1..sqrt(n)之间的整数范围,该范围将转换为类似于
for i in xrange(1, sqrt(n) + 1): ...
的值。仅此优化就大大加快了速度。你可以使用三角数公式(我直到现在才知道,谢谢你的梅花形),或者你可以使用另一种方法来找到三角数,而不是递归和字典查找。你只需要序列中的下一个数字,所以没有必要保存它。函数调用在Python中涉及很大的开销,因此递归通常不推荐用于数字处理。还有,为什么演员要
float
,我不太明白?我看到您已经在使用
xrange
而不是range
来构建int
流。我假设您知道xrange
更快,因为它是作为生成器函数实现的。你也可以这么做。这也让事情变得更加顺利。我试过这样做,使用生成器,下面的代码在我的机器(YMMV)上大约16秒内找到第500个三角形编号。但我也用了一个巧妙的技巧来找到除数,那就是quadratic sieve。
这是我的代码:
在我简陋的机器上运行它会产生以下输出:
使用三角形公式而不是简单的方法:
使用decorator(由activestate recipes提供)保存先前计算的值,并使用列表理解来生成设计器:
结果:
以及
相关问题 更多 >
编程相关推荐