const int N=1e8+79;
int n,q,k;
int prime[N],cnt;
std::bitset<N> vis;

inline void Era(int MX){
	rep(i,2,n){
		if(vis[i]) continue;
		prime[++cnt]=i;
		for(int j=i;j<=MX;j+=i){
			vis[j]=1;
		}
	}
}
int v[N];
inline void EulerSieve(int MX){
	rep(i,2,MX){
		if(!v[i]){
			v[i]=i;
			prime[++cnt]=i;
		}
		rep(j,1,cnt){
			if(prime[j]>v[i]||1ll*i*prime[j]>MX) break;
			v[i*prime[j]]=prime[j];
		}
	}
}

欧拉筛跑得比埃氏筛还慢一点。。是我的欧拉筛写的是假的吗，还是大常数版本的欧拉筛(一直都是这样写的。)