#include using namespace std; #define int long long #define INF -1145141919810 #define REP(i,n) for (int i=0;i<(n);i++) typedef pair P; int N; int dp[10001][20000]={}; vector prime; int generate(){ prime.push_back(2); for(int i=3;i<=20000;i+=2){ int k=0; for(int j=3;j<=sqrt(i);j+=2){ if(i%j==0){ k=1; break; } } if(k==0) prime.push_back(i); } return 0; } int solve(int i,int sum){ if(sum==N) return 0; if(i>prime.size()) return INF; if(sum>N) return INF; if(prime[i]>N) return INF; if(dp[i][sum]!=0) return dp[i][sum]; return dp[i][sum]=max(solve(i+1,sum+prime[i])+1,solve(i+1,sum)); } signed main(){ generate(); cin>>N; int ans=solve(0,0); if(ans