Project Euler - Probrem 46

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

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

Problem 46
Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

• 9 = 7 + 2×12
• 15 = 7 + 2×22
• 21 = 3 + 2×32
• 25 = 7 + 2×32
• 27 = 19 + 2×22
• 33 = 31 + 2×12

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数を答えよ.


－－－－－

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

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 g(n):
	import math
	L = []
	for i in xrange(1, int(math.sqrt(n//2))+1):
		s = i*i*2
		if s<=n: L.append(s)
	return L

def f():
	i = 1
	while True:
		i += 2
		P = p(i)
		if i in P: continue
		for j in g(i):
			if i-j in P: break
		else:
			return i

print f()

「平方数の2倍」と「素数」の和が「奇合成数」かを判定します。
「平方数の2倍」と「素数」の和の組合せ生成は相当の件数になるので避けます。
処理時間を短くするために、
同一範囲内では「平方数の2倍」が「素数」よりも件数が少ないことと、
奇合成数は奇数を発生させて素数リストに無い数という判定になることから、
奇数ループの中で、素数でない奇数から平方数２倍値を引いた値が素数かを判定する方法でやります。

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

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

２．関数g(n)
・n以下の「平方数の２倍値」リストを返します。

・import math
　python標準モジュールの「math」を使う準備としてインポートしておきます。

・for i in xrange(1, int(math.sqrt(n//2))+1):
　ループ変数1はカウンタです。範囲は1から上限値までです。
　上限値は、平方数の２倍がn以下ということから、n/2の平方根です。
　
・s = i*i*2
　sは平方数の２倍値です。

・if s<=n: L.append(s)
　平方数の２倍値がn以下ならば、リストLにためます。

３．関数f(n)
・i = 1
　while True:
　　i += 2
　whileの無限ループで、iは奇数カウンタでチェック対象となる値です。

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

・if i in P: continue
　奇数iが素数の場合、奇合成数ではないので次の奇数へ進みます。

・for j in g(i):
　　if i-j in P: break
　else:
　　return i

　奇数i以下の平方数２倍値リストの1つずつをループ変数jとします。
　奇数iから平方数２倍値jを引いた値が素数ならば、その奇数iは「平方数の2倍と素数の和で表せる奇合成数」なので、ゴールドバッハ予想に適合し対象外となるので次の奇数iへ進みます。
　
　for文のelse節は、for文がループの最後まで回った場合だけforループ終了後に行います。
　ここでは、ゴールドバッハ予想に適合することがなかった場合、else節に進み、奇数iを呼び出し元に返します。

３．関数の外
・print f()
　問題に合う値を表示します。


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