线性筛相比埃氏筛的核心改进在于:埃氏筛中一个合数可能被多个质数重复标记,线性筛通过"每个合数只 被其最大质因子筛去"的策略,保证每个合数恰好被标记一次,从而实现 O(n)的时间复杂度。
A:正确
B:错误
正确答案:错误
答案解析
分析线性筛的机制,观察其如何通过记录每个合数的最小质因子,使得每个合数仅在其被最小质因子作用时被标记;对比埃氏筛中合数可能被多个质因子重复标记的过程;考察线性筛在遍历过程中对每个数是否进行标记操作的条件判断逻辑,特别是当当前质数能整除该数时提前终止内层循环的设计;确认该机制是否实现了每个合数恰好被标记一次的特性,并验证其时间复杂度推导过程中对总操作次数的累加方式。
试卷来源:202603 CCF-GESP编程能力等级认证C++五级真题