使用欧拉筛解这道题

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> get_primes_less_than(int n) {
    vector<int> primes;
    vector<int> min_prime_factor(n, 0);
    for (int i = 2; i < n; ++i) {
        if (min_prime_factor[i] == 0)
            primes.push_back(i);
        for (auto p : primes) {
            if (p * i >= n)
                break;
            min_prime_factor[p * i] = p;
            if (i % p == 0)
                break;
        }
    }
    return primes;
}

int main() {
    int t;
    scanf("%d", &t);
    auto primes = get_primes_less_than(1000001);
    for (int i = 0; i < t; ++i) {
        int n;
        scanf("%d", &n);
        printf("%d\n", (int)(upper_bound(primes.begin(), primes.end(), n) -
                             primes.begin()));
    }
}