下面代码实现线性筛(欧拉筛),以筛选出 n 以内的所有素数。横线处的代码应为
vector<int> sieve(int n){
vector<bool> is_prime(n+ 1, true);
vector<int> primes;
if(n>= 0) is_prime[0]= false;
if(n>= 1) is_prime[1]= false;
for(int i= 2; i<= n;++i){
if(is_prime[i]){
primes.push_back(i);
}
for(int j= 0; j< primes.size()&& i* primes[j]<= n; j++){
is_prime[i* primes[j]]= false;
if(________________) break;//在此处填入代码
}
}
return primes;
}
i% primes[j]== 0
primes[j]% i== 0
i% primes[j]!= 0
i== primes[j]