Problem 50
41という素数は次のように連続した6個の素数の和で表せる：
41 = 2 + 3 + 5 + 7 + 11 + 13
これは最も長い連続した素数の和で100より小さい素数になるものである。
100万より小さい素数で最も長い連続した素数の和で表される数は？
http://projecteuler.net/index.php?section=problems&id=50
小さな素数から始めた方が長い素数列を取れるので、2から始まる素数列、3から始まる素数列、…というものを考えます。
100より小さいで考えましょう。リストに2と3と5から始まる素数列を入れます。そして、現在の長さを2からの素数列の最大の長さにします。2と3と5からの最大の長さは、
2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 = 77
3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 = 98
5 + 7 + 11 + 13 + 17 + 19 + 23 = 95
で、上の2つは共に長さ8です。これ以上の長さの素数列はほかにありません。そして、どちらの和も素数ではありません。
どちらの列も上から素数を削ります。ここで、5から始まる素数列の長さは一つ短い7なので、次の回に7から始まる素数列が長さ7になる可能性があるので、これもリストに加えておきます。
そして、次に長さ7の素数列を考えます。
2 + 3 + 5 + 7 + 11 + 13 + 17 = 58
3 + 5 + 7 + 11 + 13 + 17 + 19 = 75
5 + 7 + 11 + 13 + 17 + 19 + 23 = 95
7 + 11 + 13 + 17 + 19 + 23 = 90
上3つが長さ7です。そして、どの和も素数ではありません。
同じように長さ7の列は上から素数を削ります。そして、最後の7から始まる列は長さ6なので、11から始まる素数列をリストに加えます。
2 + 3 + 5 + 7 + 11 + 13 = 41
3 + 5 + 7 + 11 + 13 + 17 = 56
5 + 7 + 11 + 13 + 17 + 19 = 72
7 + 11 + 13 + 17 + 19 + 23 = 90
11 + 13 + 17 + 19 + 23 = 79
上4つが長さ6です。最初の41のみが素数なので、これが解です。
from itertools import ifilter, count, takewhile, islice
from math import sqrtdef is_prime(n):
for p in ifilter(lambda p: p * p <= n, primes):
if n % p == 0:
return False
return Truedef prime(k):
if k == len(primes):
for n in islice(ifilter(is_prime, count(primes[-1] + 1)), 1):
primes.append(n)
return primes[k]class conssecutive_primes:
def __init__(self, k0):
n = 0
for k in takewhile(lambda k: n + prime(k) <= N, count(k0)):
n += prime(k)
self.k0 = k0
self.n = n
self.l = k - k0 + 1
def next(self):
n = self.n
self.n -= prime(self.l-self.k0-1)
self.l -= 1
return n
def length(self):
return self.ldef gen_long_prime_sum():
for l in range(glist[0].length(), 0, -1):
for g in takewhile(lambda g: g.length() == l, glist):
yield g.next()
while glist[-1].length() >= l - 1:
glist.append(conssecutive_primes(len(glist)))N = 10 ** 6
primes = [ 2 ]
glist = [ conssecutive_primes(k) for k in range(3) ]
for n in islice(ifilter(is_prime, gen_long_prime_sum()), 1):
print n
