#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define RALL(x) (x).rbegin(),(x).rend() #define ALL(x) (x).begin(),(x).end() #define repp(i,n) for(int (i)=1;(i)<=(n);(i)++) #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) #define rev(i,n) for(int (i)=(n-1);(i)>=0;(i)--) #define clr(a) memset((a), 0 ,sizeof(a)) #define found(s,e) ((s).find(e)!=(s).end()) typedef pair P; typedef vector > pii; typedef map mdi; bool memo[10010]; bool dp[10010]; vector isprime(){ vector prime; for(int i=2;i<10010;i++){ if(memo[i]) continue; prime.push_back(i); for(int j=i+i;j<10010;j+=i){ memo[j]=true; } } return prime; } int main(){ vector prime=isprime(); int n; cin >> n; dp[0]=dp[1]=true; for(int i=2;i<=n;i++){ for(int j=0;j