プロジェクトオイラー Problem12

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典： 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個以上の約数をもつ最初の三角数であることが分る。
では、501 個以上の約数をもつ最初の三角数はいくらか。


私の解答例は以下のとおりです。
－－－－－

def f(n):
	m, t, L = 0, 0, []
	while len(L)<n:
		m, t, L = m+1, t+m+1, []
		for i in xrange(1, t+1):
			if t%i: continue
			elif t<i*i: break
			L += [j for j in [i, t/i] if j not in L]
	return t, m
	
a, b = f(501)
print a, ",", str(b)+"th triangle number."

－－－－－

・関数f(n)は、n個以上の約数をもつ最初の三角数を返します。

・m, t, L = 0, 0, []
　初期設定です。pythonでは複数の変数にまとめて設定できます。

・while len(L)<n:
　約数リストLの要素数がn未満の場合だけ処理を続けます。

・m, t, L = m+1, t+m+1, []
　ループ内カウンターmは、何番目の三角数かという序数です。
　m番目の三角数は、mまでの自然数の和なので、
　次の三角数（m+1番目の三角数）は、現在の三角数tと次の序数m+1の和です。
　約数リストLはクリアしておきます。

・for i in xrange(1, t+1):
　三角数tの約数リストLを作成します。約数候補iの範囲は1からtまでです。
　xrange(from, to)の第2引数toは、その値になったら処理を抜ける値なのでtでも処理を回したい場合は、その1つ先のt+1とします。

・if t%i: continue
　%演算子は割り算の余りを返します。ここでは三角数tを約数候補iで割った余りです。論理式は0:False, 0以外:Trueなので、余りがある割り切れなかった場合はcontinueで次の約数候補へ進みます。

・elif t<i*i: break
　elifは「else if」の意味でさらにチェックを続けます。
　約数候補iが約数ということは、これで割った商t/iも約数です。
　約数候補iを小さいほうから順に算出していくと、そのときの商t/iは大きいほうから順に算出できることになります。
　なので約数候補iは、最大でも自乗して三角数t未満になる場合のみで十分で、ここに達すれば約数ループは終わりにします。

・L += [j for j in [i, t/i] if j not in L]
　最初に、for文で「約数i」と「約数iで割ったときの商t/i」を取得します。
　次に、if文で約数リストLに無い場合のみ対象にします。
　そして、for文の前へ渡して計算した値（ここでは渡された値jそのもの）を要素に持つリストにして、約数リストLに結合します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
76576500 , 12375th triangle number.


（追記）
・20120715
　ソースコード部分にSyntaxHighlighterを導入。