2012年10月9日火曜日

プロジェクトオイラー 問60

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

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

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


-----

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





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

答えは合っていますが、問題では「最小のもの」を求めるところ、題意を満たす「最初のもの」を求めるプログラムです。

私の解答例は以下です。畳んでいます。
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


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

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

2.関数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を返却します。

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

・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を前後とその入れ替えの2パターンで連結し、
 int関数で数値化して、関数hで素数判定します。
 素数でなければ即終了でFalseを返します。

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

4.関数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)、未満の素数で、処理することにしました。
 求める素数が2個なら10以内の素数の組で最小組[3,7]が見つかり、
 同じく3個なら100以内の素数の組で最小組[3, 37, 67]が見つかり、
 同じく4個なら問題文にあるように1000以内の素数の組が見つかります。

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

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

・L = f(n, L+[p], p)
 1つ前の関数g()ですべて素数の場合、次に大きい素数pを候補として、さらに題意にある素数を探して追加するため、当関数f()を再帰呼び出しします。
 なお、第2引数の「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を呼び出し元に戻します。

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


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


(追記)
・20130127 ネタバレ注意の追記など

0 件のコメント:

コメントを投稿