筛质数模板

const int maxn = 1e7+10;
bool vis[maxn];
int p[maxn];
int n,cnt;
void e_sieve(int n){
	for(int i = 1;i <= sqrt(n);i++){
		if(!vis[i]){
			p[cnt++] = i;
			for(int j = i*i;j <= n;j+=i){
				vis[j] = true;
			}
		}
	}
	for(int i = 2;i <= n;i++){
		if(!vis[i]){
			p[cnt++] = i;
		}
	}
}