AstroBlog

宇宙系大学院生の戯言

Project Euler 12「高度整序三角数」をPython3で書いてみた[解答]

SPONSORED LINK

問題はこちらです。

三角数の数列は自然数の和で表わされ, 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は, 5個より多く約数をもつ最初の三角数であることが分かる.

では, 500個より多く約数をもつ最初の三角数はいくつか.

今回もほぼこちらのコピペです。
Python で Project Euler #12「高度整除三角数」 - Qiita
ただ、少しコメントを追記したので初心者の方にも少しはわかりやすくなっているかと思います。

import math

limit = 500

def compute_factors(num):   # 約数の数を計算する関数
    factors = [1]
    if(num == 1): return factors
    for i in range(2, int(math.floor(math.sqrt(num))) + 1):   #  floor(x) : x の「床」 (x 以下の最大の整数) を返す。ここでは2からnumの平方根を範囲としてiをまわす
        if(num % i == 0):   # numをiで割り切れるとき
            factors.append(i)   # append : リストに要素を追加する。これで約数がfactorに入っていく
    factors_rev = list(factors)
    factors_rev.reverse()
    for i in factors_rev:
        fac = num // i    # 整数の割り算では//を使う
        if(fac not in factors):
            factors.append(fac)   # 約数は掛け算のペアになることを利用して、大きい方の約数を同時に入れている
    return factors

triangular_nums = [1]
factors = []
n = 2
while True:
    triangular_num = triangular_nums[n-1-1] + n   # 1回目はn = 2
    triangular_nums.append(triangular_num)
    factors = compute_factors(triangular_num)
    if(len(factors) > limit):   # 約数の数がlimit(500)より大きくなったらbreak
        break
    n += 1
    
result = triangular_nums[-1]

print(result)
print(result == 76576500)
print(n)
print(factors[:20])    # 小さい方から約数20個

結果

76576500
True
12375
[1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22, 25]

処理に6秒くらい時間がかかりました。