#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int check(int vec,int n) { if(vec<=1) return 0; for(int li = 2; li<= vec/2; ++li) if(vec % li == 0) return 0; return 1; } int check(vector vec) { for(int li = 0; li< vec.size(); ++li) if(vec[li]!=1) return 0; return 1; } int Si(int n,bool prime[]) { int x=0; // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. memset(prime, true, sizeof(prime)); for (int p=2; p*p<=n; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i=p*2; i<=n; i += p) prime[i] = false; } } // Print all prime numbers for (int p=2; p<=n; p++) if (prime[p]) x++; return x; } // vectorvec(100001); int main(){ int g,zz; cin >> g; for(int a0 = 0; a0 < g; a0++){ int n,t=0,tar,i,ans; zz=0; cin >> n; bool prime[n+1]; ans=Si(n,prime); // cout<<"ANS = "<