#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include int N; //#define N 20000 using namespace std; int arr[200000]; vectorslist; bool IsPrime(int num) { if (num < 2) return false; else if (num == 2) return true; else if (num % 2 == 0) return false; // 偶数はあらかじめ除く double sqrtNum = sqrt(num); for (int i = 3; i <= sqrtNum; i += 2) { if (num % i == 0) { // 素数ではない return false; } } // 素数である return true; } //エラトステネスの篩 void Eratosthenes() { for (int i = 0; i < N; i++) { arr[i] = 1; } for (int i = 2; i < sqrt(N); i++) { if (arr[i]) { for (int j = 0; i * (j + 2) < N; j++) { arr[i *(j + 2)] = 0; } } } slist.push_back(0); for (int i = 2; i < N; i++) { if (arr[i]) { //cout << i << endl; slist.push_back(i); } } } //素数 int main(int argc, char const *argv[]) { int i, j; //int n; vector>dp(5005, vector(20005, -1)); //Eratosthenes(); cin >> N; Eratosthenes(); //dp[0][0] = 0; //dp[0][slist[0]] = 1; //int cnt = 0; //for (i = 0; i < slist.size(); i++) { for (i = slist.size() - 1 ; i >= 1; i--) { //if (arr[i] > n) break; //cnt++; dp[i][slist[i]] = max(1, dp[i][slist[i]] ); //for (j = 0; j <= N; j++) { //for (j = 0; j <= N; j++) { for (j = N; j >= 0; j--) { if (j >= slist[i] && ( dp[i][j - slist[i]] != -1) ) { //dp[i + 1][j] = max(dp[i][j] + dp[i][j - slist[i]] + 1, dp[i + 1][j] ); //dp[i + 1][j] = max(dp[i][j] + dp[i][j - slist[i]] , dp[i + 1][j]); //dp[i + 1][j] = max( dp[i][j - slist[i]] + 1, dp[i + 1][j]); //if (j - slist[i] == slist[i]) { // //dp[i + 1][j] = dp[i][j]; //} //else { // dp[i + 1][j] = max(dp[i][j], dp[i][j - slist[i]] ); //} //if (dp[i][j - slist[i]] != -1) { //dp[i + 1][j] = max(dp[i][j - slist[i]] + 1, dp[i][j]); if (j - slist[i] == slist[i]) { if (dp[i][j] != -1) { //dp[i + 1][j] = dp[i][j]; dp[i - 1][j] = dp[i][j]; } continue; } dp[i - 1][j] = max(dp[i][j - slist[i]] + 1, dp[i][j]); //} //dp[i + 1][j] = dp[i][j] + dp[i][j - slist[i]]; } else { if (dp[i][j] != -1) { //dp[i + 1][j] = dp[i][j]; dp[i - 1][j] = dp[i][j]; } } } } if (IsPrime(N) == true && dp[0][N] == -1) { //if (dp[0][N] == -1) { cout << 1 << endl; /*} else { cout << dp[0][N] + 1 << endl; }*/ } else { cout << dp[0][N] << endl; } getchar(); getchar(); return 0; }