Thought Process

My idea was to use dynamic programming, because we can build new sets from smaller sets

Like all DP problems I make an array that stores number of ways to create x

For example:
array[0] = 1, {}
array[2] = 1, {2}
array[3] = 1, {3}
array[5] = 2, {5}, {2, 3}

So I initialise the array = [1, 0, 0, ...], then I loop through each prime and find its configurations. The array has length 1548137 because (2 + 3 + 5 + ... + 4999) = 1548136 and we account for spot 0.

The general formula is array[x + p] += array[x] (Think about how to come up with this!)

In order to speed up computation there is a limit up till which I search, which is the current prime + 1, so I set curr_largest = 1. Now I loop through reversed(range(0, curr_largest)).
Yes, backwards because otherwise we will double count solutions!

Here is an illustration of how the algorithm goes

1. p = 2

   • curr_largest = 1

   • reversed(range(0, curr_largest)) = [0]

     1. array[2] = array[0 + p] = array[0] = 1 (This is saying {2} is a set whose sum is 2)

   • curr_largest += 2

2. p = 3

   • curr_largest = 3

   • reversed(range(0, curr_largest)) = [2, 1, 0]

     1. array[5] = array[2 + p] = array[2] = 1 (This is saying {2, 3} is a set whose sum is 5)

     2. array[4] = array[1 + p] = array[1] = 0 (This is there is no set whose sum is 4)

     3. array[3] = array[0 + 3] = array[0] = 1 (This is saying {3} is a set whose sum is 3)

   • curr_largest += 3

And we continue, at the end we have a complete array, where array[x] = number of sets whose sum is equal to x, then I just go through this array, check if x is prime, if it is add array[x] to a total