#include #include #include #include using namespace std; const int MAX_N = 10000; int N; vector primes(MAX_N + 1, true); vector dp(MAX_N + 1, -1); #define REP(i,first,last) for (int i=first;i> N; primes[0] = false; primes[1] = false; //-1はnil 0はfalse 1はtrue dp[0] = 1; dp[1] = 1; for (int i=2;i<=N;i++) { dp[i] = 0; vector p; if (primes[i]) { p.push_back(i); for (int j=i<<1;j<=N;j+=i) { primes[j] = false; } } for (int j=2;j