T549092 质数搜寻 题解

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e8 + 10;
bool is_prime[MAXN];

void sieve() {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAXN; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAXN; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    int t;
    cin >> t;
    sieve();
    for (int i = 0; i < t; ++i) {
        int n;
        cin >> n;
        for (int j = 0; j < n; ++j) {
            int op;
            cin >> op;
            if (op == 1) {
                int x, y;
                cin >> x >> y;
                int prime_count = 0;
                for (int num = x; num <= y; ++num) {
                    if (is_prime[num]) {
                        prime_count++;
                    }
                }
                cout << prime_count << endl;
            } else if (op == 2) {
                int z;
                cin >> z;
                vector<int> arr(z);
                for (int k = 0; k < z; ++k) {
                    cin >> arr[k];
                }
                for (int num : arr) {
                    cout << (is_prime[num] ? 1 : 0) << " ";
                }
                cout << endl;
            }
        }
    }
    return 0;
}