#include "bits/stdc++.h" using namespace std; #define print(x) cout< PI; typedef pair V; typedef vector VE; const ll mod = 1000000007; vector prime; bool is_prime[10002]; int sieve(int n){ int p=0; REP(i,n)is_prime[i]=true; is_prime[0]=is_prime[1]=false; rep(i,2,n+1){ if(is_prime[i]){ //print(i); prime.push_back(i); for(int j=2*i;j<=n;j+=i) is_prime[j]=false; } } return p; } int main(){ int n; cin>>n; int dp[20002]; bool flag[20002]; memset(dp,-1,sizeof(dp)); int p=sieve(n); dp[0]=0; for(auto u : prime){ for(int j=n;j>=0;j--){ if(u+j<=n&&dp[j]!=-1){ dp[u+j]=max(dp[u+j],dp[j]+1); } } } print(dp[n]); }