No.458

$N$ 以下の素数をエラトステネスの篩で求めておく. その $i$ 番目の素数を $p_i$ とする.

$i$ 番目の素数まで見たときに数 $j$ が何個の素数の和で表せるかを $A(i, j)$ とすると,

$$A(i, p_i) = \max(A(i-1, p_i), 1) \\ A(i, j) = \max(A(i-1, j), A(i-1, j-p_i) + 1)$$

で DP で計算できる.