# include # include # include # include # include # include # include # include # include # include # include # include # include using namespace std; using LL = long long; using ULL = unsigned long long; constexpr long long MOD = 1000000000 + 7; constexpr long long INF = 100000000000000; const double PI = acos(-1); int dp[2300][20000]; std::vector prime; void MakePrime(int n) { prime.emplace_back(2); for (int i = 3; i < n; i += 2) { bool a = false; for (int j = 3; j <= std::sqrt(i); j += 2) { if (i%j == 0) { a = true; } } if (a == false) { prime.emplace_back(i); } } } int main() { MakePrime(20000); int n; cin >> n; for (int i = 0; i < 2300; i++) { for (int j = 0; j < 20000; j++) { dp[i][j] = -1; } } dp[0][0] = 0; for (int i = 0; i < prime.size(); i++) { for (int j = 0; j <= n; j++) { if (dp[i][j] == -1)continue; if (j + prime[i] <= n)dp[i + 1][j + prime[i]] = max(dp[i + 1][j + prime[i]], dp[i][j] + 1); dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); } } cout << dp[prime.size()][n] << endl; }