using namespace std; #include #include #include #include #include int N; int dp[20009]; vector p(20009); int fanc(int i, vector p) { if (dp[i] != -1) { return dp[i]; } int res = -1; if (i == 0) res = 0; for (int j = 2; j <= N; j++) { if (p[j]==1 and (i - j) >= 0) { p[j] = 0; if (res < fanc(i - j,p) + 1) { if (fanc(i - j,p) == -1) { res = -1; } else { res = fanc(i - j, p) + 1; } } } } return dp[i] = res; } int main() { cin >> N; for (int j = 2; j <= N; j++) { for (int k = 2; k <= int(sqrt(j)); k++) { if (j % k == 0 and j != k) { p[j] = -1; break; } } if (p[j] != -1) { p[j] = 1; } } memset(dp, -1, sizeof(dp)); cout << fanc(N,p) << endl; }