欧拉计划问题12，我如何优化我的代码，让它更快地找到答案？

Question

我已经用python写了几个月了，所以请不要对我太苛刻。但我已经写了这段代码，我不知道如何才能让它更快

n = 2
ListOfTriangles = []
ListOfDivisors = []
term = 0

for x in range(1,100001):
    x = (n*(n-1))/2
    ListOfTriangles.append(int(x))
    n += 1

for y in range(1,100001):
    Tri = ListOfTriangles[term]
    for i in range(1,Tri+1):
        if(Tri%i==0):
            ListOfDivisors.append(i)
    if len(ListOfDivisors) >= 500:
        print("---------------------------------------------------")
        print(len(ListOfDivisors))
        print(ListOfDivisors)
        print(ListOfTriangles[term])
        print("---------------------------------------------------")
        break
    print(ListOfTriangles[term]," - ",len(ListOfDivisors)," - ",(term/100000)*(10**2),"%")
    ListOfDivisors = []
    term += 1

基本上，如果你不能从这个混乱中分辨出来，我所做的是，我创建了一个带有三角形数字的列表，然后将这个列表放入循环，列出列表中每个数字的所有因子，然后在找到满足500个因子以上数的要求的数字时停止

Answer 1

适用于此问题的一个想法如下：

n的第三个三角形数t[n]由n * (n + 1) / 2给出。注意n和n + 1的唯一公约数是1。设divs[n]表示n的除数。那么

• 对于偶数n，我们有divs[t[n]] = divs[n//2] * divs[n+1] - 1
• 对于奇数n，我们有divs[t[n]] = divs[n] * divs[(n+1)/2] - 1

我们可以在O(n^2)时间内预先计算从1到n的每个数字的除数（这可以渐近改进），并使用上面的公式计算相应三角形数的除数。通过numpy，我们有：

import numpy as np
# pick a number of elements for divisor computation 
n = 20_000

# store number of divisors of n; O(n^2), can be optimized asymptotically
divs = np.zeros(n+1, dtype=int)
for i in range(1,n+2):
  # i divides every number in the sequence i, 2i, 3i... (up to n)
  divs[i:n+2:i] += 1

# store number of divisors of n'th triangular number
divs_tri = np.zeros(n, dtype=int)
# treat evens and odds separately
evens = np.arange(0, n, 2) # e.g. [0, 2, 4...]
odds  = np.arange(1, n, 2) # e.g. [1, 3, 5...]
# with even k, k/2 and k+1 are coprime; -1 accounts for 1 being a factor of both
divs_tri[evens] = divs[evens//2] * divs[evens+1] - 1
# with odd k, k and (k+1)/2 are coprime; -1 accounts for 1 being a factor of both
divs_tri[odds]  = divs[odds] * divs[(odds+1)//2] - 1

# index of first triangular number with at least 500 divisors
k = (divs_tri >= 500).argmax()

# compute the value of k'th triangular number
ans = k * (k + 1) // 2