Project Euler Problem 050
http://projecteuler.net/index.php?section=problems&id=50
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2050
素数41は6つの連続する素数の和として表せる: 41 = 2 + 3 + 5 + 7 + 11 + 13. 100未満の素数を連続する素数の和で表したときにこれが最長になる. 同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ. 100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?
import math import itertools import datetime def primelist(limit=1000): checked = [ True ] * ((limit-1)/2) result = [2] for i in xrange(len(checked)): val = i * 2 + 3 if checked[i]: result.append(val) j = val + val + val while j < limit: checked[(j - 3) / 2] = False j += val + val return result def is_prime(n): if n < 2: return False if n < 4: return True if n % 2 == 0: return False if n < 9: return True if n % 3 == 0: return False r = math.floor(math.sqrt(n)) f = 5 while f <= r: if n % f == 0: return False if n % (f+2) == 0: return False f += 6 return True def euler050(): N = 1000000 l = primelist(N) x = 0 for i in xrange(len(l)): if x + l[i] > N: break x += l[i] stop = i print stop for i in xrange(len(l)): if is_prime(x): start = i print x, (start, stop), sum(l[start:stop]) break x -= l[i] begin = datetime.datetime.now() euler050() end = datetime.datetime.now() print end - begin
答え: 997651
実行時間: 0.555909秒くらい