Project Euler 12

题目

Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the $7^{\text{th}}$ triangle number would be $1+2+3+4+5+6+7=28$. The first ten terms would be: $$1,3,6,10,15,21,28,36,45,55,\dots$$ Let us list the factors of the first seven triangle numbers:

$\begin{array}{rl}\mathbf{1}:& 1\\ \mathbf{3}:& 1,3\\ \mathbf{6}:& 1,2,3,6\\ \mathbf{10}:& 1,2,5,10\\ \mathbf{15}:& 1,3,5,15\\ \mathbf{21}:& 1,3,7,21\\ \mathbf{28}:& 1,2,4,7,14,28\end{array}$

We can see that $28$ is the first triangle number to have over five divisors. What is the value of the first triangle number to have over five hundred divisors?

因数个数定理

如果一个正整数 $n$ 分解后成为： $$n=\prod _{i=1}^k{p}_i^{e_i}$$

那么 $n$ 的因数个数为： $$\prod _{i=1}^k(e_i+1)$$

解决方案

直接遍历所有的三角形数，用工具分解后，直接通过因数个数定理判断其因数个数是否超过 $500$.

代码

from tools import factorization
from itertools import count

Q = 500
for i in count(1, 1):
    x = i * (i + 1) // 2
    res = factorization(x)
    m = 1
    for p, e in res:
        m *= e + 1
    if m >= Q:
        ans = x
        break
print(ans)