A27054. 如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为O(n)。( )vector<int>linearsieve(int n){ vector<bool>is prime(n +1,true); vector<int>primes; for(inti=2;i<= n; ++i){ if(is_prime[i]){ primes.push back(i)…

如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为O(n)。(    )

vector<int>linearsieve(int n){
    vector<bool>is prime(n +1,true);
    vector<int>primes;

    for(inti=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(i%primes[j]==0){
                break;
             }
        }
    }
    return primes;
}