#include #include #include using namespace std; #define MAX_N 20001 int N; int dp[MAX_N+10][MAX_N+10]; vectorsieve(int n) { vectorprime; vectoris_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; } vectorprime=sieve(N); int number_of_prime = prime.size(); for (int i = 0; i < MAX_N + 10; i++) { for (int j = 0; j < N + 1; j++) { if (i == 0 || i == 1 ) { dp[i][j] = 0; } else { dp[i][j] = -1; } } } for (int i = 0; i <= N; i++) { for (int j = 0; j < number_of_prime; j++) { if (j - 1 >= 0 && i - prime[j] >= 0) { if (dp[i][j - 1] != -1 || dp[i - prime[j]][j - 1] != -1) { dp[i][j] = max(dp[i][j - 1], dp[i - prime[j]][j - 1] + 1); } } } } cout << dp[N][number_of_prime - 1] << endl; return 0; }