#include using namespace std; #define FOR(i,l,r) for(size_t i=(l); i<(r); i++) #define REP(i,n) FOR(i,0,n) #define endl "\n" #define debug(x) cout< Eratosthenes(int N){ vector prime(N+1,true); for(int i=2; i<=N; i++){ if(prime[i]){ for(int j=2*i; j<=N; j += i){ prime[j] = false; } } } vector res; REP(i,N+1){ if(prime[i]){ res.push_back(i); } } return res; } int main(){ int N; cin>>N; vector prime = Eratosthenes(N); vector dp(N+1,-1); dp[0] = 0; for(auto i : prime){ for(int j=N; j>=0; j--){ if(j - i < 0) continue; if(dp[j-i] == -1) continue; dp[j] = max(dp[j],dp[j-i]+1); } } cout<