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

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.

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.

download arrowUse 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.

Post a comment