#include #include typedef long long ll; typedef long double ld; using namespace std; ll prime(ll x) { ll i; if (x < 2)return 0; else if (x == 2) return 1; if (x % 2 == 0) return 0; for (i = 3; i*i <= x; i += 2) { if (x%i == 0) return 0; } return 1; } int main() { ll N; cin >> N; vectorv; for (ll i = 2; i <= 20000; i++) { if (prime(i)) { v.push_back(i); } } ll dp[20010]; for (ll i = 0; i <= 20000; i++) { dp[i] = -1; } dp[0] = 0; for (ll i = 0; i= 0; j--) { if(dp[i]==-1) continue; if (v[i] + j <= N ) { dp[j + v[i]] = max(dp[j + v[i]], dp[j] + 1); } } } cout << dp[N] << endl; }