单选题 适中
#20463

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

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

vector<int> sieve_linear(int n) {
    vector<bool> is_prime(n +1, true);
    vector<int> primes;
    if (n < 2) return primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n/2; i++) {
        if (is_prime[i])
            primes.push_back(i);
        for (int j = 0; ___________________ ; j++) { // 在此处填入代码
            is_prime[ i * primes[j] ] = false;
            if (i % primes[j] == 0)
                break;
        }
    }
    for (int i = n/2 +1; i <= n; i++) {
        if (is_prime[i])
            primes.push_back(i);
    }
    return primes;
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:C
解析

线性筛法的核心思想是 每个合数只被其最小质因数筛除一次,从而保证 O(n) 的时间复杂度。

内层循环的目的是 筛除 i×primes[j],因此需要满足:

j 不超过 primes 数组的大小(避免越界访问)。

i×primes[j]≤n(筛除的合数不能超过 n)。

本题答案为选项C。