RT，区间筛求助卡常，感觉快行了qwq

放一个可能会有用的东西，我造了一组 $K = 500k$（$k$ 为正整数）的数据qwq

代码：

#pragma GCC optimize("Ofast")

#pragma GCC target("avx")
#pragma GCC target("f16c")
#pragma GCC target("sse")
#pragma GCC target("sse2")
#pragma GCC target("sse3")
#pragma GCC target("sse4")
#pragma GCC target("sse4.1")
#pragma GCC target("sse4.2")
#pragma GCC target("ssse3")

#include <stdio.h>
#include <string.h>

typedef unsigned int uint;
typedef unsigned char uchar;

const uint N = 31622 + 7, M = 5e7 + 7, K = 1e3, block = 1e6, size = sizeof(uchar) * block;
int sqrt_r_prime[N], prime[M];
uchar bs[block + 7];
bool p[N];

inline int max(int a, int b){
	return a > b ? a : b;
}

inline void init(){
	register uint cnt = 0;
	p[0] = p[1] = true;
	for (register uint i = 2; i < N; i++){
		if (!p[i]) sqrt_r_prime[++cnt] = i;
		for (register uint j = 1; j <= cnt && i * sqrt_r_prime[j] < N; j++){
			p[i * sqrt_r_prime[j]] = true;
			if (i % sqrt_r_prime[j] == 0) break;
		}
	}
	prime[1] = 2;
	for (register uint i = 0, j = 1; i < K; i++){
		register int start = i * block, end = (i + 1) * block - 1;
		memset(bs, 0, size);
		if (i == 0) bs[1] = 1;
		for (register uint k = 2; k <= cnt && sqrt_r_prime[k] * sqrt_r_prime[k] <= end; k++){
			register int t1 = max((start - 1) / sqrt_r_prime[k] + 1, sqrt_r_prime[k]) * sqrt_r_prime[k];
			register uint t2 = sqrt_r_prime[k] * 2;
			if (!(t1 & 1)) t1 += sqrt_r_prime[k];
			for (register uint l = t1 - start; l < block; l += t2){
				bs[l] = 1;
			}
		}
		for (register uint k = 1; k < block; k += 2){
			if (!bs[k]){
				if (++j >= M) break;
				prime[j] = start + k;
			}
		}
	}
}

int main(){
	uint q;
	scanf("%u", &q);
	init();
	for (register uint i = 1; i <= q; i++){
		uint k;
		scanf("%u", &k);
		printf("%d\n", prime[k]);
	}
	return 0;
}