Project Euler - Probrem 35

Project Euler(プロジェクト　オイラー）の問題をpythonでやってみます。

出典： Project Euler（日本語 翻訳サイト）
　　　　 ProjectEuler.net（英語サイト）

Problem 35
197は巡回素数と呼ばれる.
桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.
100未満には巡回素数が13個ある:
2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.
100万未満の巡回素数は何個か?


－－－－－

def h(n):
	if n<=2: return []
	L = [2]
	for t in xrange(3, n+1, 2):
		for s in L:
			if not t%s: break
			elif t<s*s: L.append(t); break
	return L

def g(n):
	s, t, M = str(n), str(n)*2, []
	for i in xrange(len(s)):
		L = []
		for j in xrange(i, i+len(s)): L.append(t[j])
		M.append(int("".join(L)))
	return M

def f(n):
	L = set(h(n))
	return [i for i in L if set(g(i))<L]

n = 1000000
L = f(n)
print len(L), L

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

１．関数h(n)
・nまでの素数のリストを返します。
　詳しくはproblem27, problem10を参照してください。

２．関数g(n)
・巡回数のリストを返します。
・s, t, M = str(n), str(n)*2, []
　引数の数字nを文字型にしたものをs、それを２つ連結したものをtとします。
　リストMには順回数をためます。

・for i in xrange(len(s)):
　ループ変数iは、順回数の1文字目です。文字列sの1文字目から最後まで順に1文字ずつ設定します。

・L = []
　for j in xrange(i, i+len(s)): L.append(t[j])
　リストLには順回数を構成する文字を順に1つずつためます。
　ループ変数jにはi番目から元の文字列分の長さだけ、連番を設定します。
　t[j]で文字列tのj番目の文字を取得します。


３．関数f()
・主処理です。

・L = set(h(n))
　nまでの素数リストを集合型に変換します。
　集合型は集合的な演算が可能な変数型です。
　集合的な演算とは、例えば２つの集合の片方がすべて含まれるかとか、
　片方にだけある要素とか、両方にある要素の重複削除した集合、などの演算です。

・return [i for i in L if set(g(i))<L]
　内包表記です。
　まずfor文で、nまでの素数リストLから1つずつループ変数iに設定します。
　そして後ろのif文に渡し、渡された素数iの順回数のリストの要素集合が、集合Lにすべて含まれる、そのようなiだけをfor文の前に送り、そのままリストにためます。
　演算がすべて終わったら、呼び出し元にためたリストを返します。
　

４．関数の外
・関数f()で問題に合う値のリストが戻ってくるので、len関数でその要素数を計算します。


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