#include <bits/stdc++.h> using namespace std; const int maxn = 1010; long long dp[maxn]; bool is[maxn]; vector pr; void get(int n) { for (int i = 0; i <= n; ++i) { is[i] = true; } is[0] = is[1] = false; for (int i = 2; i <= sqrt(n); ++i) { if (is[i]) { for (int j = i * i; j <= n; j += i) { is[j] = false; } } } for (int i = 2; i <= n; ++i) { if (is[i]) { pr.push_back(i); } } }

int main() { int n; cin >> n; if (n < 2) { cout << 0 << endl; return 0; } get(n); dp[0] = 1; for (int p : pr) { for (int j = p; j <= n; ++j) { dp[j] += dp[j - p]; } } cout << dp[n] << endl; return 0; } [ A+B Problem PLUS]题解 原理：01背包dp