#include #include #include #include #include #include #include #include #include #include #include #include #include #define mkp make_pair #define fi first #define se second #define pt(num) cout << num << "\n" #define max(a, b) ((a)>(b) ? (a):(b)) #define min(a, b) ((a)<(b) ? (a):(b)) #define chmax(a, b) (ab ? a=b : 0) #define INF 1000000000000000000 #define MOD 1000000007LL #define MAX 100010 using namespace std; typedef long long ll; typedef pair P; typedef map Map; vector primes; void eratos(ll N) { ll isp[20202]; memset(isp, 1, sizeof(isp)); isp[0]=isp[1]=0; ll i, j; for(i=2; i*i<=N; i++) { if(isp[i]==0) continue; for(j=i+i; j<=N; j+=i) isp[j]=0; } for(i=0; i<=N; i++) if(isp[i]) primes.push_back(i); } int main(void) { ll M; cin >> M; ll i, j; ll dp[20202]; memset(dp, -1, sizeof(dp)); dp[0]=0; for(i=0; i=0; j--) { if(dp[j]!=-1) dp[j+primes[i]]=max(dp[j+primes[i]], dp[j]+1); } } pt(dp[M]); }