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

プロジェクトオイラーの問題を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)

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

１．関数p(n)

・n以下の素数リストを返します。

・問３７を流用しました。

２．関数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