// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (13 votes, average: 5.00 out of 5)

Project Euler Solutions

Project Euler 249 Solution

Project Euler 249 Solution

Project Euler 249: Prime Subset Sums

Problem Description

Let S = {2, 3, 5, …, 4999} be the set of prime numbers less than 5000.

Find the number of subsets of S, the sum of whose elements is a prime number.
Enter the rightmost 16 digits as your answer.


This problem is easy to conceptualize but difficult to get to run under one minute. I stuck with Python and there is room for optimization but it may still be a challenge. I’ll get back to it someday, which is programmer speak for “It works and I’ve got much better things to do.”

Project Euler 249 Solution

Runs < 77 seconds in Pypy.
from Euler import prime_sieve, is_prime

primes = prime_sieve(5000)
t = [1] + [0] * sum(primes)

sp = 0
for p in primes:
    sp += p
    for j in range(sp, p-1, -1):
        t[j] = (t[j] + t[j-p])

print "Project Euler 249 Solution =", (sum(t[p] for p in range(sp) if is_prime(p)) % 10**16)
download arrowUse this link to get the Project Euler 249 Solution Pypy source.


Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.


  • Pypy can shave off 40 seconds from the run time. Still too long.

Full answer:


replace the last four x’s with the last four digits of your answer.

Project Euler 249 Solution last updated


No comments yet.

Post a comment