三角数是累加自然数所得到的数。例如，第七个三角数是$1+2+3+4+5+6+7=28$，前十个三角数是: $$1,3,6,10,15,21,28,36,45,55,\ldots$$ 列举出前七个三角数的所有约数： \begin{align*} 1:&\quad 1 \\ 3:&\quad 1,3 \\ 6:&\quad 1,2,3,6 \\ 10:&\quad 1,2,5,10 \\ 15:&\quad 1,3,5,15 \\ 21:&\quad 1,3,7,21 \\ 28:&\quad 1,2,4,7,14,28 \end{align*} 可以看出，$28$是第一个含有五个以上约数的三角数。第一个约数数量超过五百的三角数是多少?

本题难度:

解答

第$n$个三角数是$n(n+1)/2$。若$m=p_1^{a_1}\ldots p_k^{a_k}$是$m$的质因数分解, 则显然$m$的约数个数是$(a_1+1)\ldots(a_k+1)$。因而与第7题中类似, 我们可以在生成三角数以及作质因数分解的同时动态更新素数表。结果是$76576500$(第$12375$个三角数)。

primeList=[2,3,5,7,11,13,17,19,23]
n=25
numDivisor=3

while numDivisor<500:
    n=n+1
    m=n*(n+1)/2
    numDivisor=1
    for p in primeList:
        a=0
        while m%p==0:
            m=m/p
            a=a+1
        numDivisor=numDivisor*(a+1)    
    if numDivisor==1:
        primeList.append(n)

print n, n*(n+1)/2