2013年5月26日日曜日

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

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

問77 「素数の和としての表し方が5000通り以上になる最初の数」
10は素数の和として5通りに表すことができる:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

素数の和としての表し方が5000通り以上になる最初の数を求めよ.

-----


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






私の回答例は以下の通りです。
def p(n):
	L = [0,0]+[1]*(n-1)
	for i in xrange(n):
		if i*i>n: break
		if not L[i]: continue
		for j in xrange(i+i, n+1, i): L[j] = 0
	return [i for i in xrange(n+1) if L[i]]

def f(n):
	c = max(100, n)
	P = p(c)
	L = [1]+[0]*c
	for i in xrange(1, c):
		if i in P:
			for j in xrange(i, c+1):
				L[j] += L[j-i]
			if L[i]-1>=n: break
		else:
			if L[i]>=n: break
	return i

n = 5000
print f(n)


問76と同様の分割数を、この問題では素数で構成します。

1.関数p(n)
・n以下の素数リストを返します。
問37を流用しました。

2.関数f(n)
・素数の和としての表し方がn通り以上になる最初の数を返します。

・返却する値の最大値を超える分だけリストを用意し、
 自然数nを素数の和で構成するパターン数をリストLに格納します。
 このリスト要素の上限数をcとして仮決めし、forループを使用しています。

・リスト要素の上限数cは100とnの大きい方の値にしています。
 理由はnが大きくなるほどmは急激に増加しm<nとなりますが、
 問題文の例のようにmが小さい場合はn<mです。
 そしてn=100のパターン数が100通り以上あるのは明らかなので、固定で100としました。
 (実際にm<nとなるのは、n>19でした)

・ループ変数iは返却値の候補です。
 素数リストに存在する値かどうかで処理が分かれます。

・iが素数の場合、パターン数リストLのi以上c以下の全要素について、自分の要素番号よりもiだけ少ない要素番号に格納されている値を足していきます。
 これによってi個手前の要素にカウントされている件数に数えられているパターンに、+iを付加した新パターンの件数を累積することになります。
 またiが素数の場合、素数だけの場合も+iしてカウントすべきパターンになるため、カウント対象外の素数だけの場合も含んでいます。
 このため、パターン数がn通り以上かの判定には、パターン数リストL[i]に格納しているパターン数から-1した値を使います。

・iが素数でない場合、パターン数リストL[i]に格納しているパターン数で判定します。

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