Project Euler 77
問題文の日本語は下のリンクから。
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2077
「素数の和としての表し方が5000通り以上になる最初の数を求めよ。」
この手の問題は再帰を使ってとくのが定石のような気がします。分割統治法って言うんだっけ？
とりあえずソースだけ載せておいて、解説はあとで書くことにします。
from number_theory import * def howmany(n, m): global many if not n: many += 1 return candidates = [x for x in range(m, n+1) if isPrime(x)] if not candidates: return for x in candidates: howmany(n - x, x) max = 0 ans = 2 while True: many = 0 howmany(ans, 2) if max < many: max = many if max > 5000: print ans break else: ans += 1
def isPrime(n): if n == 1:return False if n == 2:return True if not n % 2: return False num = 3 while num <= n**0.5: if not n % num:return False num += 2 return True
