#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1010;
int dp[N][N];
bool is_prime(int x) {
	if(x == 1) return 0;
	for(int i = 2; i * i <= x; i++) if(x % i == 0) return 0;
	return 1;
}
int dfs(int n, int s) {
//	cout << n << endl;
	if(n == 0) return 1;
	if(dp[n][s] != -1) return dp[n][s];
	int sum = 0;
	for(int i = s; i <= n; i++) {
		if(is_prime(i)) {
			sum += dfs(n - i, i);
		}
	}
	return dp[n][s] = sum;
}
signed main() {
	int n;
	cin >> n;
	memset(dp, -1, sizeof dp);
	cout << dfs(n, 2);
	return 0;
}

这份代码复杂度$O(n^3)$，居然能AC，而且无需O2优化