我在做项目欧拉问题12,并提出了以下代码,在对低数字进行测试时效果良好:
def highlyDivisibleTriangularNumber(n):
"""
triangular num formula: x(x-1)/2
e.g 5th triang num: x5 = 5(5+1)/2 = 15
:param n:
"""
divisors = [x for x in xrange(1, 31)]
count = 0
for i in xrange(1, n):
triangNum = (i* (i+1)/2) # create triangular number based on formula: x(x-1)/2
for div in divisors:
if triangNum % div == 0: # if triangular number modulo div equals 0 the add it to highestDivisors
count +=1
if count == 6: # if count is equal to 6 then we have found the required number so return it.
return triangNum
else:
if div == 30: # else if we have have reached the last divisor, reset count to zero
count = 0
print(highlyDivisibleTriangularNumber(100))
我将非常感谢您对如何提高效率的一些建议,我在哪里出错,以及在设置除数上限方面。 我确信从数学的角度来看,无疑有许多方法可以改进代码。 谢谢。在
三角形数序列是由自然数相加生成的。所以第七个三角形是1+2+3+4+5+6+7=28。前十个术语是:
1,3,6,10,15,21,28,36,45,55。。。在
让我们列出前七个三角形数的因子:
1比1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21:1,3,7,21 28:1,2,4,7,14,28 我们可以看到28是第一个有5个以上除数的三角形数。在
第一个有超过500个除数的三角形数的值是多少?在
大约需要5-10秒,不是很快,但可以接受。在
下面所示的代码避免了前面介绍的代码中存在的几个问题。在
原始post中的一个问题是通过测试所有小于正在处理的}之间的数字不需要测试),但回报率会迅速减少。更重要的加速是使用divisor function的乘法形式;例如,如果一个数
t
的数字来计算除数。存在各种可能的加速:不要测试(t+2)/2
和t-1
之间的数字,因为它们都不能除以t
。这可以扩展(例如,(t+3)/3
和{t
等于pᵃ·qᵇ·rᶜ
带p, q, r
素数,然后σ₀(t) = τ(t) = (a+1)·(b+1)·(c+1)
。(除数计数函数σ₀(sigma zero)通常用τ(tau)表示,而不是σ₀。)另一个答案中的一个问题是在每个步骤中}进行因式分解。在每个步骤中只考虑},并记住上一步中的因子会更快。这样可以将执行时间缩短至少2倍。在
(i*(i+1)/2)
或{i+1
或{下面的代码通过}比{}小。在
τ(k)·τ(k+1)·e/(e+1))
计算τ(k·(k+1)/2)
,其中e
表示乘积τ(k)·τ(k+1)
中2的指数。也就是说,因为k
的素因子不能是k+1
的素因子,反之亦然,τ(k·(k+1)) = τ(k)·τ(k+1)
;并且{当
findHiTau(120)
调用时,附加的程序在我的旧计算机上运行大约0.14秒。findHiTau
的参数是程序oddprimes
表中素数大小的上限,是被测试的k
的最高值的平方根;因此将处理大约k⁴/2
的三角形数。在相关问题 更多 >
编程相关推荐