基础数学知识

果然还是又一出写一出的比较适合我，按计划写博客没有一点点动力

素数筛

虽然筛法很多，但我觉得也没必要把那么多些都写这儿，毕竟到时候用也只会用最好的那种
所以这里就只写线性筛法：欧拉筛
欧拉筛和埃氏筛有点相似，都是用比较小的素数来标记合数，但不同的是埃氏筛中一个合数可能被多个素数访问，比如12就可能被2和4都访问到，欧拉筛则避免了这种情况。欧拉筛的精髓在于他只让某个合数的最小质因数访问它并标记。比如12就只能被2* 6标记。那么是怎么做到的呢？
首先是比较常规的is_prime数组标记和存答案的prime数组以及存答案个数的cnt
首先将1标记为非素数，然后外层i从2到n循环，若is_prime[i]未被标记则加入答案数组。然后内层从1到cnt循环j，让i与已得到的质数一一相乘。在遍历的过程中如果i能被prime[j]整除则在标记后跳出循环。
原因：如果i能整除以prime[j],说明i的倍数也一定是prime[j]的倍数。我们之前说过，某个合数只会被它的最小质因子标记，那么显然不可能是被i标记。所以为了避免重复标记，直接跳出循环
以下为输出n以内第k大素数的代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e8+5;
bool is_prime[maxn];
int prime[maxn];
int n,q,cnt=0;
void pre()
{
	is_prime[1]=true;
	for(int i=2;i<=n;i++)
	{
		if(!is_prime[i]) prime[++cnt]=i;
		for(int j=1;j<=cnt;j++)
		{
			if(i*prime[j]>n) break;
			is_prime[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&q);
	pre();
	for(int i=1;i<=q;i++)
	{
		int x;
		scanf("%d",&x);
		printf("%d\n",prime[x]);
	}
	return 0;
}