Project Euler Problem 12

高度整除三角数

三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である.
三角数の最初の10項は:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる.

最初の7項について, その約数を列挙すると, 以下のとおり.
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
これから, 7番目の三角数である28は, 6個以上の約数をもつ最初の三角数であることが分かる.

では, 500個以上の約数をもつ最初の三角数はいくつか.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2012

Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th 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, ...

Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
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?

http://projecteuler.net/problem=12

考え方

自然数 n が、

( は素数、 は 0 以上の整数)
と素因数分解されるとき、n の約数の個数と 約数の総和は、次の公式で与えられる。
約数の個数：
約数の総和：

たとえば、 は、 と素因数分解され、約数は、






で、約数の個数 は、 個、
約数の総和は


である。