单选题
适中
#19816
下述代码实现素数表的线性筛法,筛选出所有小于等于 的素数,则横线上应填的代码是( )。 vector < int > linear_sieve ( int n…
下述代码实现素数表的线性筛法,筛选出所有小于等于 的素数,则横线上应填的代码是( )。
答案与解析
正确答案:A
解析
线性筛法通过标记合数的方式筛选素数,确保每个合数仅被其最小质因子筛除一次。外层循环遍历从2到n的整数i,若i未被标记,则将其加入素数表。内层循环需枚举已记录的素数j,用i与j的乘积标记合数,且当j能整除i时应终止以保证线性时间复杂度。内层循环的上限为当前已知素数个数,循环变量j作为素数列表的索引使用。