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

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

問８７「3つの素数のべき乗」
素数の2乗と素数の3乗と素数の4乗の和で表される最小の数は28である. 
50未満のこのような数は丁度4つある.

28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24

では, 50,000,000未満の数で, 素数の2乗と素数の3乗と素数の4乗の和で表される数は何個あるか?





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






私の回答例は以下の通りです。

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):
	P, L = p(int((n-2**3-2**4)**.5)), []
	for i in P:
		for j in P:
			for k in P:
				s = k**2+j**3+i**4
				if n<=s: break
				L.append(s)
	return len(set(L))

n = 50000000
m = f(n)
print m

１．関数p(n)
・n以下の素数リストを返します。問３７を流用しました。

２．関数f(n)
・素数の2乗と素数の3乗と素数の4乗の和で表されるn未満の数の個数を返します。

・Pに素数、Lには素数の2乗と素数の3乗と素数の4乗の和を格納します。
　ただし、使用する最大の素数は、自身の2乗と2の3乗と2の4乗の和がn未満になる最大素数なので、nから2の3乗と2の4乗を差し引いた値の平方根の整数部分です。
　この使用可能な最大素数までの素数をリストPに格納します。

・素数リストLから、3重のfor文でi,j,kとして順番に1つずつ、重複を許して取り出し、それぞれを2乗、3乗、4乗して、その和を変数sとします。

・変数sがnを超えたら、それ以上のkのループは不要なのでkのfor文を終了します。
　j,kのループにも同様の判定を入れることは可能ですが、1分ルールをクリアしたのでこのままとします。
　

・return len(set(L))
　set文でリストLの要素の値をユニークにして、len関数で個数を数えて戻します。

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