#include #include #include #include #include #include #include #include #include #include #include #include #include #define mkp make_pair #define pr(num) cout << num << "\n" #define max(a, b) ((a)>(b) ? (a):(b)) #define min(a, b) ((a)<(b) ? (a):(b)) #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 isprime[N+5]; memset(isprime, 1, sizeof(isprime)); ll i, j; isprime[0]=isprime[1]=0; for(i=2; i*i<=N; i++) { if(!isprime[i]) continue; for(j=i+i; j<=N; j+=i) { if(j%i==0) isprime[j]=0; } } for(i=2; i<=N; i++) { if(isprime[i]) primes.push_back(i); } } int main() { ll N; cin >> N; ll dp[N+5]; eratos(N); memset(dp, 0, sizeof(dp)); for(ll p : primes) { for(ll i=0; i<=N; i++) { if(dp[i]!=-1 && i+p<=N) { dp[i+p]=max(dp[i+p], dp[i]+1); } } } pr(dp[N]); }