#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define Rep(b, e, i) for(int i = b; i <= e; i++) #define Repr(e, b, i) for(int i = e; i >= b; i--) #define rep(n, i) Rep(0, n-1, i) #define repr(n, i) Repr(n-1, 0, i) #define all(v) (v).begin(), (v).end() #define pb(v) push_back(v) #define uniq(v) (v).erase(unique(all(v)),(v).end()) #define bitcnt(x) __builtin_popcount(x) #define fst first #define snd second #define Pqaz(T) priority_queue,greater> #define Pqza(T) priority_queue #define put(x) cout << x; #define putsp(x) cout << x << ' '; #define putln(x) cout << x << endl; #define ENJYU std::ios::sync_with_stdio(false);std::cin.tie(0); typedef long long ll; typedef pair llP; typedef pair intP; typedef complex comp; //vector の中身を出力 template ostream &operator<<(ostream &o,const vector&v) {o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<> N; memset(prime, true, sizeof(prime)); prime[0] = prime[1] = false; for (int i = 2; i < MAX; i++) { if (!prime[i]) continue; for (int j = 2; i * j < MAX; j++) { prime[i*j] = false; } } vector ps; rep(MAX, i) { if (prime[i]) ps.pb(i); } int l = (int)ps.size(); //dp[i][j] := i版めまでのj個使って memset(dp, -1, sizeof(dp)); dp[0][0] = 0; rep(l, i) rep(MAX, j) { dp[i+1][j] = max(dp[i+1][j], dp[i][j]); if (ps[i] + j < MAX) { dp[i+1][j+ps[i]] = max(dp[i][j] + 1, dp[i+1][j+ps[i]]); } } cout << (dp[l][N] >= 0 ? dp[l][N] : -1) << endl; } int main(void){ solve(); //cout << "yui(*-v・)yui" << endl; return 0; }