原创 | codeforces 1424J，为了过这题，我把祖传的C++都用上了！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
// 一些宏定义
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
using namespace std;
const int N=1000050;
const long long Mod=1000000007;
int t, query[N];
int isprime[N], primecnt[N];


// 埃式筛法
void eratosthenes() {
    rep(i, 0, N) isprime[i] = 1;
    rep(i, 2, N) {
        if (isprime[i]) {
            for (int j = i+i; j < N; j += i) {
                isprime[j] = 0;
            }
        }
    }
    // 维护质数的前缀和
    rep(i, 2, N) {
        primecnt[i] = primecnt[i-1] + isprime[i];
    }
}


int main() {
    eratosthenes();
    scanf("%d", &t);
    rep(i, 0, t) {
        int query;
        scanf("%d", &query);
        printf("%d\n", primecnt[query] - primecnt[int(sqrt(query))] + 1);
    }
    return 0;
}