判断题 偏易
#20475

线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。( )

线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。( )

未登录也能判分,登录后才会记录
答案与解析
正确答案:对
解析

线筛的时间复杂度是 O(n),每个合数只被其最小质因数筛去一次。

而埃筛的时间复杂度是 O(nlog log n),相对来说会更高,是在筛选过程中存在重复操作。

本题答案为正确。