プロジェクトオイラー12.

この記事の所要時間: 135

No.12 Highly divisible triangular number

問題.

Q. 三角数 とは, 1 からの連続した自然数の和で表される数です. 例えば 7 番目の三角数は,

\begin{align*}
1+2+3+4+5+6+7 = 28
\end{align*}

で, 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

正の約数の個数が 5 個を初めて超えるのは 28 です.

では, 正の約数の個数が初めて 500 個を超える三角数は?

考え方とプログラム例(Python)

正の約数の個数を求める関数

num_of_divisors()

を定義します.

約数をすべて実際に数えるのではなく, 公式を使います.

自然数 \(n\) が

\begin{align*}
n = p_1^{q_1}\cdot p_2^{q_2}\cdots p_N^{q_N}
\end{align*}

(\(p_1, \ldots, p_N\) は異なる素数)

と素因数分解されるとき,

約数の個数 num_of_divisors(n) は,

num_of_divisors(n) = \((q_1+1)(q_2+1)\cdots(q_N+1)\)

となることを利用します

計算時間は 4.15 秒でした.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加