✏️ 纠错
第 208 题 / 共 251 题
7、函数linearSieve实现线性筛法(欧拉筛)，横线处应填入（ ）。
你真棒！
📝 题目解析
【答案】A
【考纲知识点】线性筛（欧拉筛）
【解析】线性筛的核心是每个合数都用自己的最小质因子标记，保证每个数字只会被标记一次，从而达到O(n)的时间复杂度。当i能被当前质数p整除时（i%p==0）说明i已经包含了p作为最小质因数，此时如果继续用更大的质数乘i进行标记，就会造成重复标记。
【考纲知识点】线性筛（欧拉筛）
【解析】线性筛的核心是每个合数都用自己的最小质因子标记，保证每个数字只会被标记一次，从而达到O(n)的时间复杂度。当i能被当前质数p整除时（i%p==0）说明i已经包含了p作为最小质因数，此时如果继续用更大的质数乘i进行标记，就会造成重复标记。