プロジェクトオイラー 問６０

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

問６０　「任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の組を求めよ」
素数3, 7, 109, 673は非凡な性質を持っている.
任意の2つの素数を任意の順で繋げると, また素数になっている.
例えば, 7と109を用いると, 7109と1097の両方が素数である.
これら4つの素数の和は792である.
れは, このような性質をもつ4つの素数の組の和の中で最小である.

任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の組の和の中で最小のものを求めよ.

－－－－－

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





最初にコーディングしたときにfor文の五重ループになってしまったので、どうしても再帰関数に改良したかったことと、処理速度の向上とで、１ヶ月近くかかってしまいました。
上限値を設けてやっと１分ルールを満たしているので、まだまだロジックが甘いのですが、行き詰まってしまったこともあり、現在のプログラムのまま提示しておきます。
答えは合っていますが、問題では「最小のもの」を求めるところ、題意を満たす「最初のもの」を求めるプログラムです。

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

def h(n):
	if n==2: return True
	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 e(n):
	i = n+1+int(n%2)
	while not h(i): i += 2
	return i

def g(L, t):
	t = str(t)
	for s in L:
		s = str(s)
		if not h(int(s+t)): return False
		if not h(int(t+s)): return False
	return True

def f(n, L=[], p=0):
	if len(L)>=n: return L
	while p<10**(n-1):
		p = e(p)
		if g(L, p):
			L = f(n, L+[p], p)
			if len(L)>=n: break
	else:
		L.pop()
	return L

n = 5
s = f(n)
print sum(s), s

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

１．関数h(n)
・素数判定です。問５８で作成したものを流用しました。
　素数ならTrue、素数でなければFalseを返します。

２．関数e(n)
・引数を超える最小の素数を返します。n>1のとき有効です。

・i = n+1+int(n%2)
　変数iが素数候補です。
　%演算子は割り算の余りです。割り切れれば0、割り切れないと1なので、
　式全体では偶数なら1足し、奇数なら2足すことになります。
　後続処理の準備として、素数候補iを奇数にしておきます。

・while not h(i): i += 2
　関数h()で素数判定をして、素数でなければ2ずつ増やしてチェックします。
　前準備でこの処理にくるときには素数候補iは奇数にしているので、
　iが偶数で無限ループになることはありません。

・return i
　ここまでの処理でnを超える最初の素数としてiを返却します。

３．関数g(L, t)
・引数リストLの各要素と引数tを任意の順に２つ連結した値が、すべて素数かどうかを判定します。

・t = str(t)
　後で連結するので、引数tを文字型にします。

・for s in L:
　引数リストLから順にループ変数sに設定します。

・s = str(s)
　後で連結するので、ループ変数sを文字型にします。

・if not h(int(s+t)): return False
　if not h(int(t+s)): return False
　上記の文字列sと文字列tを前後とその入れ替えの２パターンで連結し、
　int関数で数値化して、関数hで素数判定します。
　素数でなければ即終了でFalseを返します。

・return True
　引数リストLと引数tでここまでで処理を抜けていなければ、そのすべての組合せが素数なので、Trueを返します。

４．関数f(n, L=[], p=0)
・問題に合う値のリストを返します。
　自分で自分を呼び出す記述のある再帰関数です。
　引数nは求める素数の個数です。
　引数Lは素数を格納するリストで初期値は空リストです。
　引数pは最後にチェックした素数で、初期値は0とします。

・if len(L)>=n: return L
　再帰関数の終了条件です。
　リストLに求める個数n個以上の要素がたまったら処理終了で、リストLを返します。

・while p<10**(n-1):
　対象とする素数が青天井では処理が終わらないので、とりあえず求める素数の個数分の桁数、10**(n-1)、未満の素数で、処理することにしました。
　求める素数が２個なら10以内の素数の組で最小組[3,7]が見つかり、
　同じく３個なら100以内の素数の組で最小組[3, 37, 67]が見つかり、
　同じく４個なら問題文にあるように1000以内の素数の組が見つかります。

・p = e(p)
　得られている最後の素数pを関数eで処理し、次に大きい素数を改めてpとします。

・if g(L, p):
　関数gで引数リストLの各要素と引数pを任意の順に２つ連結した値が、すべて素数かどうかを判定します。Falseの場合はwhileループの次の値へ進みます。

・L = f(n, L+[p], p)
　１つ前の関数g()ですべて素数の場合、次に大きい素数pを候補として、さらに題意にある素数を探して追加するため、当関数f()を再帰呼び出しします。
　なお、第２引数の「L+[p]」は、再帰呼び出しで引数Lで受けるので、お試しでリストLの末尾に追加することになります。

・if len(L)>=n: break
　再帰呼び出しから戻り、リストLの要素数がn以上ならば探索終了でwhileループから抜けます。

・else:
 L.pop()
　このelse節はインデント（行頭のずらし位置）から明らかなように、for文のelseです。直前のif文のelse節ではありません。
　for文のelse節の処理タイミングは、forループの最後の値まで処理が行われた場合のループ終了直後です。
　ここまでの処理でbreakで抜けない場合、再帰呼び出しの際にお試しで追加したpが求める値ではないということになります。
　このため、関数pop()で末尾の要素を削除しておきます。

・return L
　処理の最後にリストLを呼び出し元に戻します。

５．関数の外
・n = 5
　s = f(n)
　print sum(s), s
　問題に合うように引数の値を5として関数f()を呼び出します。
　返されたリストをsとして、そのリスト要素合計、及び参考としてリスト要素を表示します。


　
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
26033 [13, 5197, 5701, 6733, 8389]

（追記）
・20130127　ネタバレ注意の追記など