1到N全部质数
const int N=sqrt(1E9);
vector<int>isprime(N+1,1);
vector<int>primes;//质数存放
void init(){
for(int i=2;i<=N;i++){
if(isprime[i])
primes.push_back(i);
for(auto p : primes){
if(i*p>N) break;
isprime[i*p]=0;
if(i%p==0) break;
}
}
}
const int N=sqrt(1E9);
vector<int>mp(N+10);//数字i的最小质因子
vector<int>primes;//质数存放
void init(){
for(int i=2;i<=N;i++){
if(!mp[i])
{ primes.push_back(i);
mp[i]=i;
}
for(auto p : primes){
if(i*p>N) break;
mp[i*p]=p;
if(i%p==0) break;
}
}
}