质数筛

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e7 + 10;
int p[N], cnt, minp[100000010];
bool t[100000010];
void prime(int n) {
    for (int i = 2; i <= n ; i ++) {
        if (!t[i]) {
            p[cnt ++] = i;
            minp[i] = i;
        }
        for (int j = 0; p[j] * i <= n; j ++) {
            //p[j] <= n / i 等同于 p[j] * i <= n，而p[j] * i就是所有要筛除的合数。减少了不必要的计算.
            t[p[j] * i] = true;
            minp[i * p[j]] = p[j];
            if (i % p[j] == 0) {
                break;//保证筛掉的是合数，并且是用最小质因子筛的
            }
        }
    }
}
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    prime(n);
    while (q --){
        int x;
        scanf("%d", &x);
        printf("%d\n", p[x - 1]);
    }
    return 0;
}