#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef vector vi; #define rep(i,x) for(int i=0;i<(int)(x);++i) int main(){ int n; cin >> n; vector isprime(n+1, true); isprime[0] = false; for (int i=2; i