计算第一个三角数在python中具有超过500个除数 [英] Calculating the first triangle number to have over 500 divisors in python

问题描述

我正在尝试解决Euler项目上的第12个问题.我可以计算出将近4分钟内有500个除数的数字.我怎样才能使其更快?这是尝试；

I'm trying to solve the 12th problem on Project Euler. I can calculate the number that has over 500 divisors in almost 4 minutes. How can i make it faster? Here's the attempt;

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*(n+1)/2，在其中找到第n个三角数.

You don't need an array to store the triangle numbers. You can use a single int because you are checking only one value. Also, it might help to use the triangle number formula:n*(n+1)/2 where you find the nth triangle number.

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

getD also only needs to return a single number, as you are just looking for 500 divisors, not the values of the divisors.

但是，您真正的问题出在for循环中的n/2上.通过检查因子对，可以使用sqrt(n).因此，仅检查不超过sqrt(n)的值.如果最多检查n/2，则会浪费大量的测试(以百万计).

However, your real problem lies in the n/2 in the for loop. By checking factor pairs, you can use sqrt(n). So only check values up to sqrt(n). If you check up to n/2, you get a very large number of wasted tests (in the millions).

因此，您想执行以下操作(n是用于求除数的整数，d是可能的除数):

So you want to do the following (n is the integer to find number of divisors of, d is possible divisor):

• 确保n/d没有余数.
• 确定是在除数中添加1还是2.

• make sure n/d has no remainder.
• determine whether to add 1 or 2 to your number of divisors.

这篇关于计算第一个三角数在python中具有超过500个除数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！