// 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.

download arrowUse this link to get the Project Euler 249 Solution Pypy source.


  • 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