Project Euler 249

プロジェクトオイラー
http://projecteuler.net/

Q249.
5000より小さい素数の集合をSとする。その要素の和が素数となるSの部分集合の個数を、下16桁で答えよ。

この問題は易しい。
部分集合の要素の和→個数というマップを作る。和のうち素数のものの個数を足し合わせる。
最初、dictを使っていたが、listで十分。メモリ使用量が少なくて済む。

from itertools import ifilter, imap
def is_prime(n):

    if n < 2:

        return False

    

    for p in S:

        if p * p > n:

            return True

        elif n % p == 0:

            return False

    return True
def make_primes(limit):

    for n in xrange(3, limit + 1, 2):

        if is_prime(n):

            S.append(n)
def num_subset_prime_sum(S):

    a = [ 1 ] + [ 0 ] * sum(S)

    max_sum = 0

    for p in S:

        for s in xrange(max_sum, -1, -1):

            a[s+p] += a[s]

        max_sum += p

    return a
def num_prime(a):

    return sum(imap(lambda n: a[n], ifilter(is_prime, xrange(len(a)))))
N = 5000

S = [ 2 ]

make_primes(N - 1)

print num_prime(num_subset_prime_sum(S)) % 10 ** 16