下列线性筛的代码片段中,当枚举到质数p且i%p==0时,使用break;语句停止继续枚举。这样做的主要目的是()
for(int i= 2; i<= n;++i){
if(!is_composite[i])
primes.push_back(i);
for(int p: primes){
if(i*p> n)
break;
is_composite[i*p]= true;
if(i% p== 0)
break; //这条语句的目的是?
}
}
保证递归深度不超过O(log n)
保证每个合数只被它的最小质因子筛去一次
保证每个素数都被标记为合数
把筛法时间复杂度提高到O(n log n)