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

この記事の所要時間：約 1分51秒

No.12 Highly divisible triangular number

問題.

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

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

で, 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{equation*} n = p_1^{q_1}\cdot p_2^{q_2}\cdots p_N^{q_N} \end{equation*}$

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

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

約数の個数 num_of_divisors(n) は,

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

となることを利用します

def num_of_divisors(n):
	Num = 1
	i = 2
	while n != 1:
		num = 1
		while n % i == 0:
			n /= i
			num += 1
		Num *= num
		i += 1
	return Num
n = 1
while True:
	Tn = n * (n + 1) / 2
	if num_of_divisors(Tn) > 500:
		print Tn
		break
	n += 1

def num_of_divisors(n):

Num = 1

i = 2

while n != 1:

num = 1

while n % i == 0:

n /= i

num += 1

Num *= num

i += 1

return Num

n = 1

while True:

Tn = n * (n + 1) / 2

if num_of_divisors(Tn) > 500:

print Tn

break

n += 1

計算時間は 4.15 秒でした.

答えはこの下の行にあります. 反転してください.

A. 76576500 (12375番目の三角数)

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

No.12 Highly divisible triangular number

問題.

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

共有:

関連

関連記事