python - 计算第一个三角形数在python中有超过500个除数

Question

我正在尝试解决 Project Euler 的第 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)

Answer 1

您不需要数组来存储三角形数。您可以使用单个 int，因为您只检查一个值。此外，使用三角形编号公式可能会有所帮助:n*(n+1)/2 您可以在其中找到第 n 个三角形编号。

getD 也只需要返回一个数字，因为您只是在寻找 500 个除数，而不是除数的值。

但是，您真正的问题在于for 循环中的n/2。通过检查因子对，您可以使用 sqrt(n)。所以只检查小于等于 sqrt(n) 的值。如果检查到 n/2，您会得到大量浪费的测试(数百万)。

所以你要执行以下操作(n 是要查找除数的整数，d 是可能的除数):

• 确保n/d没有余数。
• 确定是将 1 还是 2 添加到除数中。