https://www.acwing.com/activity/content/problem/content/937/
埃氏筛
#include <iostream>
using namespace std;
const int N = 1e6 + 10; // 定义数组大小
int st[N]; // 定义一个 bool 类型的数组，用于标记每个数是否为质数
int primes[N]; // 定义存储素数的数组
int cnt; // 定义计数器，记录素数个数
int n; // 定义素数上限
void get_primes(){ // 获取素数函数
for(int i = 2;i<=n;i++){ // 从 2 到 n 枚举每个数
if(!st[i]){ // 如果当前枚举的数 i 是质数
primes[cnt++] = i; // 将 i 加入素数数组
for(int j = i;j<=n;j+=i) st[j] = true; // 将 i 的倍数标记为合数
}
}
}
int main(void) {
cin>>n; // 读入素数上限
get_primes(); // 获取素数
cout << cnt << endl; // 输出素数个数
return 0; // 返回值表示程序正常结束
}
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e8 + 10;
int st[N];//定义一个 bool 类型的数组，用于标记每个数是否为质数
int prime[N];
int idx,cnt;
/*
埃拉托斯特尼筛法（又名埃氏筛），是一种用来找出一定范围内所有质数的算法，由古希腊数学家埃拉托斯特尼提出。
该算法的基本步骤如下：
1. 首先将所有的数标记为质数。
2. 从最小的质数2开始，标记它的所有倍数为合数，因为它的所有倍数都不可能是质数。
3. 在剩下的数中，找到下一个最小的没有被标记为合数的数，即为下一个质数。
4. 如此重复以上步骤，直到所有小于或等于n的数都被标记。
埃氏筛最直观的实现方式是从2开始，将2的所有倍数都标记为合数，然后是3，下一个然后是5，以此类推。这种方式虽然简便，但效率较低，因为有许多数被重复标记。
在实际处理中，我们在找到一个质数后，只需要从这个质数的平方开始标记，因为比它小的倍数已经被之前的质数标记过了。这样，每个合数都被其最小的质因数标记，所以时间复杂度为O(n)。
更多细节和进阶的优化，可以查看[维基百科上的埃拉托斯特尼筛法条目](https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95)。
*/
void get_primes(int n) {
for(int i = 2;i<=n;i++) {
if(!st[i]){
prime[cnt++] = i;
for(int j = i;j<=n;j+=i){
st[j] = true; //把i得倍数标记位合数
}
}
}
}
/*
线性筛法，也叫做欧拉筛法，是一种用来筛选素数的算法，
其主要优点是每一个数在筛选过程中都只会被它的最小素因子访问到，一共就 n 个数，
所以时间复杂度是 O(n)，这是一个线性的时间复杂度，在处理大规模的素数筛选问题时，可以更有效地利用内存、提高计算效率。
线性筛法的步骤如下：
首先将所有的数标记为质数。
然后从最小的质数2开始，枚举到n，如果当前数i是质数，那么就把它加入到质数列表中。
对于每个质数列表中的元素p，找出所有大于等于p且小于等于n/p的自然数i，并且标记p*i为合数。
如果i可以被p整除，那么之后的p'*i (其中p'是大于p的质数）实际上已经被p标记过了，此时可以提前结束循环。
这样操作的好处在于每个数在筛选过程中被访问的次数都是常数次，所以这个筛法的时间复杂度是线性的。这在处理大规模的素数筛选问题时是非常实用的。
*/
void get_prime(int n)
{
for(int i = 2; i <= n; i ++) {
if(!st[i]) prime[idx ++] = i;
for(int j = 0; prime[j] <= n / i; j ++) {
st[prime[j] * i] = true;
if(i % prime[j] == 0) break;
}
}
}
int main(){
int n,q;
scanf("%d %d",&n,&q);
get_prime(n);
for(int i = 0;i<q;i++) {
int k;
scanf("%d",&k);
printf("%d\n",prime[k - 1]);
}
}