Project Euler - Problem 50

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

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

Problem 50
素数41は6つの連続する素数の和として表せる:
41 = 2 + 3 + 5 + 7 + 11 + 13.
100未満の素数を連続する素数の和で表したときにこれが最長になる.

同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

－－－－－


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

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 f(n):
	P = p(n)
	i, s, t = 0, 0, 0
	while s<n: i, s = i+1, s+P[i]
	for j in xrange(i):
		if i-j<t: break
		for k in xrange(i-1, j, -1):
			if k-j<t: break
			L = P[j:k+1]
			if sum(L) in P: M, t = L, len(L)
	return M

L = f(1000000)
print sum(L)
print "sum of "+str(len(L))+" consecutive primes, " \
+ "from "+str(L[0])+" to "+str(L[-1])+"."

連続する素数和が100万未満ということなので、
まず100万までの素数リストを作ります。
次にこの素数リストの小さい方から和が100万未満となる最大位置を把握します。
そしてこの最大位置までの範囲内で連続する区間を短くしならがその和が、
素数リストにあるかチェックするという流れでやります。

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

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

２．関数f(n)
・n以下の素数を連続する素数の和で表したときに最長になる素数のリストを返します。
　問題では100万未満ですが、100万は明らかに素数ではないのでこのまま使用します。

・P = p(n)
　n以下の素数リストです。

・i, s, t = 0, 0, 0
　初期設定です。0クリアしておきます。

・while s<n: i, s = i+1, s+P[i]
　iはカウンター、sは素数表のi番目までの和です。
　この和がnを超えたらループ終了です。
　カウンターiが、連続素数和の構成に使用できる最大位置となります。

・for j in xrange(i):
　　if i-j<t: break
　ループ変数jは、連続素数和の最小値の位置です。
　範囲は0から使用最大位置iの1つ手前までです。
　tは後で出てきますが、連続素数の候補の連続する個数です。
　i-jが現在のjの値を固定したときに使用できる素数の最大件数なので、
　i-j<tになったら現在調査済みの連続個数を超えられないのでループをは終了します。

・for k in xrange(i-1, j, -1):
　　if k-j<t: break
　ループ変数kは、連続素数和の最大値の位置です。
　範囲は上記最小値の位置jの１つ手前から使用できる最大位置iの1つ手前までです。
　大きい順にチェックするので、開始位置と終了位置を入れ替えて刻みを-1にしています。
　k-jが現在のkの値を固定したときに使用できる素数の最大件数なので、
　k-j<tになったら現在調査済みの連続個数を超えられないのでループをは終了します。

・L = P[j:k+1]
　リストLは上記の位置jと位置kの範囲で素数表Pから取り出した連続素数のリストです。

・if sum(L) in P: M, t = L, len(L)
　連続素数リストLの合計が素数表Pにあれば、連続素数リストLを連続素数最大長リストMとして、また連続数をtとして保存します。

・return M
　上記のループがすべて終了した時点で、連続素数最大長リストMを呼び出し元へ返します。

３．関数の外
　100万を関数fに渡し、100万未満の素数を連続する素数の和で表したときに最長になる素数のリストを受け取ります。
求める値はこのリストの和、sum(L)です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
997651
sum of 543 consecutive primes, from 7 to 3931.