#4145. [GESP202603 七级 C++] 第 2 题

[GESP202603 七级 C++] 第 2 题

下面关于"唯一分解定理"和"素数筛法"的说法中,错误的是( )。

{{ select(1) }}

  • 如果预处理出 nn 以内每个数的最小质因子,那么可以在 O(logn)O(\log n) 时间内完成任意一个不超过 nn 的整数的质因数分解。
  • 线性筛(欧拉筛)能够保证每个合数只被其最小质因子筛掉一次,这一性质依赖于唯一分解定理。
  • 唯一分解定理保证:若一个数未被任何不超过其平方根的质数筛去,则它一定是质数。
  • 唯一分解定理是埃氏筛时间复杂度为 O(nloglogn)O(n \log \log n) 的根本原因。