2012年8月14日火曜日

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


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

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

2.関数g(n)
・巡回数のリストを返します。

・s, t, M = str(n), str(n)*2, []
 引数の数字nを文字型にしたものをs、それを2つ連結したものを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番目の文字を取得します。


3.関数f()
・主処理です。

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

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

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


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

0 件のコメント:

コメントを投稿