Please list the language used, number of lines of code, and running time (if measurably greater than zero).
Let p_1 = 2, p_2 = 3, ..., p_172 = 1021 be the first 172 primes. We will denote the number of subsets of {p_1, p_2, ..., p_k} that sum to n by D(k, n).
We know that D(0, 0) = 1 and D(0, n) = 0 if n > 0.
Also note that D(k, n) = D(k-1, n) + D(k-1, n-p_k). This comes from the fact that each subset S of {p_1, ..., p_k} can either contain p_k or not. If p_k is in S then S\{p_k} sums to n-p_k and there are D(k-1, n-p_k) such S\{p_k}. If p_k is not in S then S is made entirely of elements from {p_1, ..., p_{k-1}}, obviously there are D(k-1, n) such S.
We can use the base case and this recurrence to fill our dynamic programming table D(k, n). The answer to the original problem is D(0, p_1) + D(1, p_2) + ... + D(171, p_172).
My program implements this approach except that it fills D(k, n) by rows and doesn't keep the whole table in memory.
Perl, 7s. Looks like I arrived at the same recurrence that madars used, but I swear I didn't look at his solution...
Memoize magically turns it from exponential to polynomial.