#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; typedef vector V; typedef complex Point; #define PI acos(-1.0) #define EPS 1e-10 const ll INF = 1e16; const ll MOD = 1e9 + 7; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define rep(i,N) for(int i=0;i<(N);i++) #define ALL(s) (s).begin(),(s).end() #define EQ(a,b) (abs((a)-(b)) prime; bool is_prime[20000 + 1]; int sieve(int n){ int p = 0; for (int i = 0; i <= n; i++)is_prime[i] = 1; is_prime[0] = is_prime[1] = 0; for (int i = 2; i <= n; i++){ if (is_prime[i]){ prime.push_back(i); for (int j = 2 * i; j <= n; j += i)is_prime[j] = 0; } } return p; } ll dp[20000+1][2]; int main(){ cin >> n; sieve(20000); rep(i,20000+1)rep(j,2)dp[i][j] = -1; dp[0][0] = 0; rep(i,prime.size()){ rep(j,n){ if(dp[j][i%2] == -1)continue; if(j+prime[i] <= n){ dp[j+prime[i]][(i+1)%2] = max(dp[j+prime[i]][i%2],dp[j][i%2]+1); } dp[j][(i+1)%2] = max(dp[j][(i+1)%2],dp[j][i%2]); } } cout << dp[n][n%2] << endl; }