#include using namespace std; bool isPrime(int n){ if(n == 0 || n == 1) return false; else if(n == 2 || n == 3 || n == 5) return true; else if(n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false; else{ for(int i=7;i * i <= n;i+=2){ if(n % i == 0) return false; } } return true; } int main(){ int n; cin >> n; vector prime; for(int i=2;i <= 20001;i++){ if(isPrime(i)) prime.push_back(i); } vector dp(20010,-1); dp[0] = 0; for(auto p: prime){ for(int j = n;j >= 0;j--){ if(p + j <= n && dp[j] != -1){ dp[p+j] = max(dp[p+j],dp[j] + 1); } } } cout << dp[n] << endl; }