#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; for (int i=2;i<=MAX_N;i++) { if (primes[i]) { for (int j=i*2;j<=MAX_N;j+=i) { primes[j] = false; } } } //-1はnil 0はfalse 1はtrue dp[0] = 1; dp[1] = 1; for (int i=2;i<=N;i++) { dp[i] = 0; for (int j=2;j