对于正整数 n, 求 n 以内的(包括 n)素数个数。

#include <iostream>

#include <vector>

using namespace std;

vector<int> sieve(int n) {

vector<bool> is_prime(n + 1, true);

is_prime[0] = is_prime[1] = false;

for (int i = 2; i * i <= n; ++i) {

if (is_prime[i]) {

for (int j = i * i; j <= n; j += i) {

is_prime[j] = false;

}

}

}

vector<int> prime_count(n + 1, 0);

for (int i = 2; i <= n; ++i) {

prime_count[i] = prime_count[i - 1] + is_prime[i];

}

return prime_count;

}

int main() {

int t;

cin >> t;

vector<int> prime_count = sieve(1000);

while (t--) {

int n;

cin >> n;

cout << prime_count[n] << endl;

}

return 0;

}