#include #include #include #include using namespace std; #define MAX_N 20001 int N; // int dp[MAX_N + 10][MAX_N + 10]; vector sieve(int n) { vector prime; vector is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { prime.push_back(i); for (int j = 2 * i; j <= n; j += i) { is_prime[j] = false; } } } return prime; } int main() { cin >> N; // if (N == 1) { // cout << -1 << endl; // return 0; // } vector prime = sieve(N); int number_of_prime = prime.size(); vector> dp(N + 1, vector(number_of_prime + 1, -1)); for (int i = 0; i <= 0; i++) { for (int j = 0; j <= number_of_prime; j++) { dp[i][j] = 0; } } for (int i = 0; i <= N; i++) { for (int j = 0; j < number_of_prime; j++) { //dp[i][j + 1] = dp[i][j]; if (i - prime[j] >= 0 && dp[i - prime[j]][j] != -1) { dp[i][j + 1] = max(dp[i][j ], dp[i - prime[j]][j] + 1); } } } // for (int i = 0; i <= N; i++) { // for (int j = 0; j < number_of_prime; j++) { // cout << setw(3) << dp[i][j]; // } // cout << endl; // } cout << dp[N][number_of_prime] << endl; return 0; } // dp[i][j]は和がiになるもので、j番目の要素まで使った場合の最大の素数の数 // dp[i][j]=max(dp[i][j-1],dp[i-xj][j-1]+1);