## 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

Runs < 77 seconds in Pypy.Use this link to get the Project Euler 249 Solution Pypy source.

#### Afterthoughts

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

Full answer:

18089131734384088361396707178609119521538648663874965565252

81728260738457913373744890199439933572129728883223063765155

24683070889481179665713632474523500808965429134707479096569

03114415927526256425xxxx

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

*Project Euler 249 Solution last updated*

## Discussion

## No comments yet.