线性筛代码

关键在于：每个合数只被它最大的非自身的因数筛掉。

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100000001,inf=0x3f3f3f3f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
int n,q,prms[N],tot;
//1不是0是 
bool prm[N];
int main(){
	n=read(),q=read();
	prm[0]=prm[1]=1;
	fs(i,2,n,1){
		if(!prm[i]) prms[tot++]=i;
		for(ll j=0;j<tot&&i*prms[j]<=n;j++){
			prm[i*prms[j]]=1;
			if(i%prms[j]==0) break;//保证了每个数只会被筛一次
		}
	}
	while(q--){
		int p=read();
		printf("%d\n",prms[p-1]);
	}
	return 0;
}