单选题
适中
#20463
下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数,横线上应填的最佳代码是?( ) vector < int > sieve_linear ( int…
下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数,横线上应填的最佳代码是?( )
答案与解析
正确答案:C
解析
线性筛法的核心思想是 每个合数只被其最小质因数筛除一次,从而保证 O(n) 的时间复杂度。
内层循环的目的是 筛除 i×primes[j],因此需要满足:
j 不超过 primes 数组的大小(避免越界访问)。
i×primes[j]≤n(筛除的合数不能超过 n)。
本题答案为选项C。