单选题 适中
#19816

下述代码实现素数表的线性筛法,筛选出所有小于等于 的素数,则横线上应填的代码是( )。 vector < int > linear_sieve ( int n…

下述代码实现素数表的线性筛法,筛选出所有小于等于 的素数,则横线上应填的代码是( )。

vector<int> linear_sieve(int n) { 
    vector<bool> is_prime(n +1, true); 
    vector<int> primes; 
    is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理 
    for (int i = 2; i <= n; ++i) { 
        if (is_prime[i]) { 
            primes.push_back(i); 
    } 
    ________________________________ { // 在此处填入代码 
        is_prime[ i * primes[j] ] = 0; 
        if (i % primes[j] == 0) 
            break; 
        } 
    } 
    return primes; 
}


未登录也能判分,登录后才会记录
答案与解析
正确答案:A
解析
线性筛法通过标记合数的方式筛选素数,确保每个合数仅被其最小质因子筛除一次。外层循环遍历从2到n的整数i,若i未被标记,则将其加入素数表。内层循环需枚举已记录的素数j,用i与j的乘积标记合数,且当j能整除i时应终止以保证线性时间复杂度。内层循环的上限为当前已知素数个数,循环变量j作为素数列表的索引使用。