GESP 七级 · GESP 202603 C++ 七级 第 2 题

下面关于“唯一分解定理”和“素数筛法”的说法中，错误的是（ ）。

埃氏筛法：从2开始标记倍数为合数，O(n log log n)。线性筛（欧拉筛）：每个合数只被最小质因子标记一次，O(n)。线性筛效率更高。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】唯一分解定理｜线性筛｜埃氏筛

🎯 考纲定位 本题核心考查唯一分解定理与筛法复杂度的深层关联。命题人专挑"定理作为算法依据"的模糊边界设坑，多数考生误以为筛法复杂度源于定理，实则混淆了数论基础与算法效率。

🧠 解题思维 逐项拆解：A选项利用最小质因子预处理，每次除法至少减半，log n步必分解完毕，正确；B选项线性筛的本质就是保证每个合数只被其最小质因子筛去一次，这直接源于唯一分解定理的"最小质因子唯一性"，正确；C选项"不超过√n的质数筛不去即为质数"是试除法的核心依据，唯一分解定理保证了若为合数必含≤√n的质因子，正确；D选项把筛法复杂度归因于唯一分解定理，这是严重的概念错位——埃氏筛O(nloglog n)源于调和级数求和∑(n/p)，与分解定理无关。

🪤 陷阱拆解 陷阱最险在D项——它偷换了"筛法复杂度来源"的概念。命题人利用考生对数论定理的熟悉感，将"唯一分解定理"这个数论基石与"筛法时间复杂度"这个算法效率强行绑定。实际上，筛法复杂度O(nloglog n)来自调和级数求和∑(p≤n;n/p)，与分解定理毫无关系；而分解定理真正支撑的是B项"最小质因子唯一性"和C项"试除法边界"。考生若只背结论、不理解定理在算法中的真实作用，必会误选D。

🔄 反命题思维 若把D项改为"唯一分解定理是埃氏筛能筛到n的根本原因"，答案才成立，但原句错在将"定理"与"复杂度"挂钩。刷到类似题先问：这道题考的是数论定理本身，还是定理在算法中的实际作用？命题人最爱用"定理是算法依据"这种模糊表述设陷阱。