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{aligned} \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{aligned}\)

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)