[Project Euler] Project Euler Problem 12
Pythonで実装。おそらく、安直に書くと計算が終わらない最初の問題かも?
引数の数が500を超える最初のtriangle numberは何か?という問題。
まず、triangle numberは、ある整数nを用いて、
と書ける。
ここで、nとn+1は互いに素であることに注目しよう。一般に、ある整数nの約数の数をF(n)と表現することにすると、nとmが互いに素なら
である。
さらに、nとn−1の必ずどちらかは偶数で、どちらかを2で割っても依然として互いに素である。よって、
(nが偶数の時)
または
(nが奇数の時)
と表せる。
普通なら、分解されたF(n)等は真面目に計算するしかないが、ここでは二つの工夫をすることによって計算量を劇的に減らすことが出来る。
- 一度計算した約数の個数は、保存しておいて再利用する
- もし、nや(n+1)/2等の数が、再び m(m+1)のかたちで表せるなら、前出の式が再び適用できる(このパターンは意外に多い)
これらを実装すれば、Pythonで書いても計算は一瞬で終わる。というわけでソースコード。
import math import sys fact = {1:1, 2:2} # 約数の個数をキャッシュする辞書 def num_factors(n): if n in fact: return fact[n] r = int(math.sqrt(n)) num = 0 if r * (r+1) == n: num = num_factors(r) * num_factors(r+1) else: i = 1 while i < r: if n % i == 0: num += 1 i += 1 num *= 2 if r*r == n: num += 1 fact[n] = num return num def main(): n = 2 while True: if n % 2 == 0: fn = num_factors(n/2) * num_factors(n+1) else: fn = num_factors(n) * num_factors((n+1)/2) if fn >= 500: print "%d = (%d * %d)/2, it has %d factors" % (n*(n+1)/2, n, n+1, fn) return fact[n * (n+1)/2] = fn n += 1 if __name__ == '__main__': main()