Prime Sum Decomposition

Problem Background

Special for beginners, ^_^

Problem Description

Any natural number $N>1$ can be written as a sum of primes each between $2$ and $N$ (including the case of a single number), and there may be more than one such prime-sum expression. For example, $9$ has four essentially different prime-sum expressions: $$9 = 2+5+2 = 2+3+2+2 = 3+3+3 = 2+7$$

Two expressions are considered essentially the same if one can be obtained from the other simply by reordering the terms.

Write a program to compute how many essentially different prime-sum expressions a natural number $N$ can be written as.

Input Format

Multiple test cases. Each line contains one natural number $N$, $2\le N\le 200$.

Output Format

For each natural number $N$, output the number of essentially different prime-sum expressions, one per line.

Sample Input 1

2

Sample Output 1

1

Sample Input 2

200

Sample Output 2

9845164

Constraints

$2\le N\le 200$.

Time limit 1s, memory limit 1024KiB for each test case.

Hint

Approach 1:

Step 1 – Divide into stages by the primes used.

Step 2 – Define state: f[i][j] = number of ways to make sum $j$ using the first $i$ primes.

Step 3 – Transition: $f[i][j]=\sum_{k=0}^{\lfloor j/p[i]\rfloor}f[i-1][j-k\ast p[i]]$, where $p[i]$ is the $i$-th prime.

Step 4 – Initial value: f[0][0]=1.

Approach 2:

Transition: f[i][j] = f[i-1][j] + f[i][j-p[i]]; // for $j\ge p[i]$