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.

Analysis

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

Afterthoughts

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

18089131734384088361396707178609119521538648663874965565252
81728260738457913373744890199439933572129728883223063765155
24683070889481179665713632474523500808965429134707479096569
03114415927526256425xxxx

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