线性筛素数（欧拉筛）

这题n很大

用埃式筛 O ( n   l o g l o g   n ) O(n ~log log ~n) O(n loglog n)还是会超时的

所以就用线性筛 O ( n ) O(n) O(n)

#include
using namespace std;
int n,q,tot,prime[6000005];
bool a[100000005];
void primes()//线性筛
{
	for(int i=2;i<=n;i++)
	{
		if(a[i]==0)prime[++tot]=i;
		for(int j=1;j<=tot;j++)
		{
			if(prime[j]>n/i)break;
			a[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&q);
	primes();
	while(q--)
	{
		int x;
		scanf("%d",&x);
		printf("%dn",prime[x]);
	}
	return 0;
}