プロジェクトオイラー 問５８

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。

問５８「渦巻きに配置された格子の対角線上にある素数の数を調べ上げよ」
1から始めて, 以下のように反時計回りに数字を並べていくと,
辺の長さが7の渦巻きが形成される.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

面白いことに, 奇平方数が右下の対角線上に出現する.
もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である.
ここで割合は8/13 ≒ 62%である.

渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る.
以下, この操作を繰り返していく.

対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.

－－－－－


注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。





私の解答例は以下です。畳んでいます。

def h(n):
	if n<2 or (not n%2): return False
	for i in xrange(3, n, 2):
		if i*i>n: break
		if not n%i: return False
	return True

def g(n):
	if n<1 or (not n%2): return []
	elif n==1: return [1]
	s, t = n-1, n-2
	u = t*t+s
	return [u, u+s, u+s*2, u+s*3]

def f(p):
	i, u = 1, 0
	while not (0<float(u)/(4*(i//2)+1)<p):
		i += 2
		u += len([j for j in g(i) if h(j)])
	return i

p = 0.1
print f(p)

３つの関数を使っています。

１．関数h(n)
・素数判定です。2と、3以上の奇数で割り切れるか判定します。

・if n<2 or (not n%2): return False
　2以下、または2で割り切れる場合、素数ではありません。
　%演算子は割り算の余り、余り0は論理的にFalseです。

・for i in xrange(3, n, 2):
　素因数候補として、3以上の奇数を順にループ変数iに設定します。
　割り切り判定の割る数として使用します。
　終了値をnにしていますが、後続ロジックでnになる前に必ずループを終了します。

・if i*i>n: break
　引数nを構成する素因数の限界値は√nです。これを超える素因数はあり得ません。そこで、素因数候補がこの限界値まで達したら、ループを抜けます。

・if not n%i: return False
　割り切り判定です。割り切れたら、素数でないのでFalseを返します。
　%演算子は割り算の余り、余り0は論理的にFalseです。

・return True
　割り切れる素因数候補が無く、素数なのでTrueを返します。

２．関数g(n)
　問２８では同じ渦巻きの四隅和を返す関数を作りましたので、
　これの返り値を四隅和から四隅値のリストに修正しました。

３．関数f(n)
・問題文の渦巻きについて、対角線上の値のうち素数の割合が引数p未満になる最初の辺の長さを返します。

・i, u = 1, 0
　初期設定です。iは渦巻きの辺の長さ、uは対角線上の素数の個数です。

・while not (0<float(u)/(4*(i//2)+1)<p):
　「float(u)/(4*(i//2)+1)」は、対角線上の素数の割合です。
　この値が0と引数pの間に入ったら、ループ終了です。
　uは対角線上の素数の個数で、割り算で小数点以下まで求めるので、float関数で浮動小数点型にしています。
　「(4*(i//2)+1)」は対角線上の値の個数です。辺の長さiにより決まります。

・i += 2
　辺の長さは渦巻きを1つ巻くごとに、2ずつ増えます。

・u += len([j for j in g(i) if h(j)])
　内包表記です。
　for文で関数g(i)にて取得した辺の長さiの四隅値の1つひとつをループ変数jに設定し、後ろのif文に渡し、関数h(j)にて素数判定し素数だけをfor文の前に渡します。
　for文の前はjをリスト化し、len関数でその要素数を数えて、uに累積します。

・return i
　whileループ終了時点の辺の長さiを呼び出し元に返します。

４．関数の外
・p = 0.1
　print f(p)
　問題に合うように10%＝0.1を関数fに渡し、その返り値を表示します。
　
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
26241
（追記）
・20130129　ネタバレ注意の追記など