#include using namespace std; #define ll long long #define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++) template bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0; i < v.size(); ++i) { os << v[i]; if (i != v.size() - 1) os << ' '; } return os; } vector prime(int n) { assert(n>=2); vector ok(n+1, true); ok[0] = ok[1] = false; for (int i=1; i*i<=n; i++) { if (!ok[i]) continue; for (int j=i*2; j<=n; j+=i) { ok[j] = false; } } vector ret; for (int i=2; i<=n; i++) if (ok[i]) ret.push_back(i); return ret; } int main() { int n; cin >> n; auto P = prime(n); int m = P.size(); vector dp(n+1, -1); dp[0] = 0; // cout << dp << endl; for (auto p: P) { // cout << p << endl; for (int i=n; i>=0; i--) { if (dp[i]==-1) continue; if (i+p<=n) { chmax(dp[i+p], dp[i] + 1); // cout << "\t" << i << "\t" << dp << endl; } } } cout << dp[n] << endl; return 0; }