Project Euler - Probrem 41

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

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

Problem 41
n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつもつこととする.

#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁Pandigital数であり, かつ素数である.

n桁（この問題の定義では9桁以下）Pandigitalな素数の中で最大の数を答えよ.


－－－－－

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

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 g(n):
	import itertools
	t = "".join([str(i) for i in xrange(1, n+1)])
	return [int("".join(s)) for s in itertools.permutations(t, n)]

def f(n):
	M = []
	for i in xrange(1, n+1):
		#print i
		L = p(10**(i//2+1))
		for j in g(i):
			for k in L:
				if not j%k: break
			else:
				M.append(j)
	return M

L = f(9)
print L[-1]

problem37の素数リストを、problem38のpandigital数判定すればできるかと
思いましたが、そもそも9桁の素数リストがメモリエラーで作成できませんでした。
そこで方針を変えて、9桁以下のpandigital数を生成しこれを素数判定することにしました。
３つの関数を使っています。

１．関数p(n)
・n以下の素数リストを返します。problem37と同じです。

２．関数g(n)
・n桁のpandigital数のリストを返します。

・import itertools
　pythonの標準モジュール「itertools」をインポートします。

・t = "".join([str(i) for i in xrange(1, n+1)])
　1からnまでの数字を文字型にして、区切り文字無しで連結します。
　例えば、n=9ならばt="123456789"になります。

・return [int("".join(s)) for s in itertools.permutations(t, n)]
　標準モジュールitertoolsの関数permutations(t, n)は、
　文字列tの構成文字列から繰り返しを許さずにn個を選んで組にして返します。
　例えば、t="122",n=2ならば、("1","2")("2","1")を返します。

　ここでは、上記の「繰り返しを許さない順列タプル」をfor文で1つずつループ変数sとして、このタプルsを区切り文字無しで連結しint関数で数字型にしてリストにためます。
　例の場合、[12, 21]となります。
　
３．関数f(n)
・n桁以下のpandigitalな素数のリストを返します。

・for i in xrange(1, n+1):
　ループ変数iは桁数です。値の範囲は1からnまでです。

・L = p(10**(i//2+1))
　関数p(n)による素数リストです。
　最大値の平方根まであれば十分なので、上限値は半分の桁数+1桁分の、10の累乗です。

・for j in g(i):
　ループ変数jは、i桁のpandigital数です。

・for k in L:
　　if not j%k: break
　else:
　　M.append(j)

　ループ変数kは、チェックで使用する素数です。
　%演算子は割り算の余りです。
　for文のelse節は、for文がループの最後まで回った場合だけforループ終了後に行います。
　ここでは、割り切れて余りが0（論理的にFalse）の場合、素数ではないので、kのfor文を終了し、1つ上のjのfor文の次の値に進みます。
　kのfor文が最後の要素まで全部終わった（途中のifでひっかからなかった）場合が素数です。
　この場合はelse節に進み、リストMにjをためます。

・return M
　上記の要領でためたpandigitalな素数リストMを呼び出し元に返します。

２．関数の外
・L = f(9)
　リストLは9桁以下のpandigitalな素数リストです。

・print L[-1]
　最大の値はリストLの最後の要素です。
　リスト[-1]で最後の要素を取得します。

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