题解 | 【模板】质数判定Ⅱ ‖ 批量查询：线性筛

#include <bits/stdc++.h>
using namespace std;
using ll=long long; // 简化long long类型书写

const ll MAXN = 20000000; // 质数筛选最大范围
vector<ll> primes;         // 存储筛出的所有质数
vector<bool> is_prime(MAXN + 1, true); // 标记是否为质数，初始默认是质数

// 欧拉筛（线性筛）预处理质数
void sieve() {
    is_prime[0] = is_prime[1] = false; // 0和1不是质数
    for (ll i = 2; i <= MAXN; ++i) {   // 遍历2~MAXN所有数
        if (is_prime[i]) {
            primes.push_back(i);       // 未被标记则是质数，加入数组
        }
        for (ll p : primes) {          // 用已筛质数标记合数
            if (i * p > MAXN) break;   // 超出范围则终止
            is_prime[i * p] = false;   // 标记i*p为合数
            if (i % p == 0) break;     // 保证仅被最小质因子标记
        }
    }
}

int main() {
    ios::sync_with_stdio(false); // 关闭IO同步，提升速度
    cin.tie(nullptr);            // 解除cin与cout绑定

    sieve(); // 预处理所有质数

    ll T;
    cin >> T;
    while (T--) {                // 处理T次查询
        ll o;
        cin >> o;
        if (o == 1) {            // 操作1：查询第k小质数
            ll k;
            cin >> k;
            cout << primes[k-1] << '\n'; // 数组0索引，取k-1位置
        } else if (o == 2) {     // 操作2：判断x是否为质数
            ll x;
            cin >> x;
            cout << (is_prime[x] ? "YES\n" : "NO\n"); // 直接查标记数组
        }
    }
    return 0;
}