プロジェクトオイラー Problem3

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


出典：Project Euler（日本語翻訳サイト）
参考：サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 3
13195 の素因数は 5、7、13、29 である。
600851475143 の素因数のうち最大のものを求めよ。

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

def f(n):
	a, p, b, q = 2, n, n, n
	while a<=b:
		if q%a: a += (a%2 + 1)
		else: p, b, q = a, b/a, q/a
	return p
	
print f(600851475143)

－－－－－

処理本体は関数fに記述し、答えをprint文で出力します。

やり方は最大素数の候補pを、その最小値候補aと最大値候補bで挟み、その範囲を狭くしていって、最小値候補a≦最大値候補bが成り立たなくなったら終了というものです。

１．whileループの前の変数初期化
　以下の４つの変数を１行で初期化しています。
・a：最大素因数の最小値候補です。初期値は最小の素数である2です。
・p：求める素因数です。引数そのものが素数である場合が最大なので初期値はnです。
・b：最大素因数の最大値候補です。初期値は引数nです。
・q：割り切れるかの判定対象値です。初期値は引数nです。

次にwhileループの中の処理です。
２．割り切り判定
　%演算子は割り算の余りを返し、論理判定では0がFalse、0以外がTrueと判定されます。
　if文の条件式q%aでは、Trueが割り切れない場合で、Falseが割り切れる場合です。

３．判定対象値qが最小値候補aで割り切れないとき
　最小値候補aを次に大きい値に進めて、whileループの先頭に戻ります。
　最小値候補aは素数を小さい順に試せばいいのですが、処理を簡単にするためにここでは「２と３以上の奇数」を順に試しています。
　この方法で素数は必ず含みますが、9や15などの素数ではない数でも割り切れるか余分に判定することになります。
　
　(a%2 + 1)は、2で割り切れると1、2で割り切れないと2になります。

　a += でaに次々に加算していきます。
　最初にa=2の場合、a=2+1=3が次の最小候補値aになります。
　次にa=3の場合、a=3+2=5というように、この後は3以上の奇数が順に最小値候補aになります。

４．判定対象値qが最小値候補aで割り切れるとき
　以下の設定をして、whileループの先頭に戻ります。
・p：最大素因数候補pは、割り切ることができたその割った値aです。
・b：最大素因数の最大値候補bは、割り切れた数の分だけ小さな値b/aで十分です。
・q：この割り切り判定の商q/aが次の判定対象値です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
6857


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