Project Euler - Probrem 37

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

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

Problem 37
3797は面白い性質を持っている. まずそれ自身が素数であり,
左から右に桁を除いたときに全て素数になっている(3797, 797, 97, 7).
同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない.
総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.
－－－－－

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

def p(n):
	L = [0,0]+[1]*(n-1)
	i = 2
	while i*i<=n:
		while not L[i]: i += 1
		for j in xrange(i+i, n+1, i): L[j] = 0
		i += 1
	return [i for i in xrange(n+1) if L[i]]

def hl(n):
	s = str(n)
	L = [int(s[i:]) for i in xrange(len(s))]
	return L

def hr(n):
	s = str(n)
	L = [n]+[int(s[:-i]) for i in xrange(1, len(s))]
	return L

def g(L, M): return [int(str(s)+str(t)) for s in L for t in M]

def f():
	L = [2, 3, 5, 7]
	R = [1, 3, 7, 9]
	N = []
	i = 1
	while len(N)<11:
		i += 1
		P, L, Mr, Ml = set(p(10**(i))), g(L, R), [], []
		for s in L:
			if set(hr(s))<P: Mr.append(s)
			if set(hl(s))<P: Ml.append(s)
		N += sorted(set(Mr)&set(Ml))
	return N

L = f()
print sum(L), L

問題に合う素数は11個しかないという記述を受けて、11個見つかれば処理終了にしています。
当初は、提示された個数を終了条件にせず、右から切り詰めた値と左から切り詰めた値から問題に合う値が無いところまで処理して、結果として11個でしたという方法を狙っていました。
しかしこの方法では上限が1億以上となる素数リストが必要で1分ルールを守れず断念しました。

ここでは５つの関数を使っています。

１．関数p(n)
・n以下の素数を返します。

・problem7、problem10、problem27、problem35を改良して速度向上を図りました。
割り算をなくし、「エラトステネスのふるい(wikipedia)」のロジックで素数が1つ確定したらその倍数は素数ではないとフラグを立てていきます。
そして最後に連番とフラグリストからから素数を抽出する方法にしました。
これで前のロジックの約10倍の速度に改良できました。

・L = [0,0]+[1]*(n-1)
　リストLのi番目が数値iが素数かどうかの判定結果を持ちます。
　0と1は素数の対象外なので0として、それ以降は素数候補として全部1にしておきます。

・i = 2
　2から順に素数判定します。

・while i*i<=n:
　素数iは二乗して上限値n以下である必要があるので、これを終了判定に使用します。

・while not L[i]: i += 1
　リストLで素数フラグが0になっているものは読み飛ばし、素数iを探します。

・for j in xrange(i+i, n+1, i): L[j] = 0
　iは素数なのでiのフラグは1のままにしておき、iより大きいiの倍数である、i+iからnまでi刻みのフラグに0を設定します。
　
・i += 1
　次の値の判定に進みます。

・return [i for i in xrange(n+1) if L[i]]
　内包表記です。
　0からnまでの値のうち、リストLに1が立っている値（論理判定でTrue）だけを抽出したリストを返します。

２．関数hl(n)
・nを左から切り詰めた値のリストを返します。

・s = str(n)
　str関数で文字型変数sにしておきます。

・L = [int(s[i:]) for i in xrange(len(s))]
　内包表記です。
　ループ変数iとして0から文字数分の整数を発生させ、
　s[i:]で位置i以降の文字列を取り出しリストにためます。

３．関数hr(n)
・nを右から切り詰めた値のリストを返します。
　関数hl(n)とほぼ同じです。
　s[:-i]で右からの位置iまでの文字列を取り出してリストにためます。
　i=0のときに文字列全体ではなく空文字になるので、nは別途リストに足します。

４．関数g(L, M)
・return [int(str(s)+str(t)) for s in L for t in M]
　リストLの要素の右側にリストMの要素を組み合わせて結合し数値型にしてためたリストを返します。
　二重ループの内包表記です。
　リストLの要素をs、リストMの要素をtとして、for文の前に渡し、結合した値を作ります。

５．関数f(n)
　問題に合う素数の範囲を絞るにあたり、一番左の桁に置くことができる数字Lと、Lの右に置くことができる数字Rに分けて、LにRを次々と右に連結していくことで問題に合う候補を発生させていきます。

・L = [2, 3, 5, 7]
　一番左に置ける数字のリストです。1桁の素数です。

・R = [1, 3, 7, 9]
　Lの右に置ける数字のリストです。5以外の奇数です。2桁以上の数字で1桁目が5の場合はすべて素数ではありません。

・while len(N)<11:
　ループ開始と終了条件です。問題のとおりに11個たまったら終了とします。

・i += 1
　iは求める素数の桁数です。少ない桁から順に桁数を増やしていきます。

・P, L, Mr, Ml = set(p(10**(i))), g(L, R), [], []
　Pは素数判定する際の素数リストで、i桁をすべて含む値としてその上限値は10のi乗です。set文で集合型に変換しておきます。
　LはリストLの要素の右にリストRの要素を連結したリストで、ループの都度、リストRの要素が右に継ぎ足されていきます。

・for s in L:
　上記で作成した候補リストLの要素をsとして、問題に合うか判定します。

・if set(hr(s))<P: Mr.append(s)
　if set(hl(s))<P: Ml.append(s)
　右から切り詰めた値がすべて素数ならば、リストMrにためます。
　右から切り詰めた値のリストをset文で集合型にして、集合Pにすべて含まれたらリストMrにためます。
　左から切り詰めた値も同様にリストMlにためます。
　
・N += sorted(set(Mr)&set(Ml))
　上記のリストMr、Mlを集合型にして、&演算子で両方に含まれる要素の集合を作成します。
　これで右から切り詰めても左から切り詰めてもすべて素数になる値だと判定できます。
　このような値をsorted関数で小さい順に並べて、リストNにためます。
　　
６．関数の外
・関数f()で問題に合う値のリストが戻ってくるので、sum関数でその合計を計算します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
748317 [23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]