caioj 1157 线性筛选素数

注意这道题开得非常大，有2*1e7

自己可以养成一种习惯，如果数据是很容易的话，可以自己手动输入极限数据来测试自己的程序

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 21234567;
bool is_prime[MAXN];
vector<int> prime;void get_prime()
{memset(is_prime, true, sizeof(is_prime));is_prime[0] = is_prime[1] = false;REP(i, 2, MAXN){if(is_prime[i]) prime.push_back(i);REP(j, 0, prime.size()){if(i * prime[j] >= MAXN) break;is_prime[i * prime[j]] = false;if(i % prime[j] == 0) break;}}
}int main()
{get_prime();int n;scanf("%d", &n);while(n--){int x; scanf("%d", &x);printf("%d\n", prime[x-1]);}return 0;
}