判断题
偏易
#20475
线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。( )
线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。( )
答案与解析
正确答案:对
解析
线筛的时间复杂度是 O(n),每个合数只被其最小质因数筛去一次。
而埃筛的时间复杂度是 O(nlog log n),相对来说会更高,是在筛选过程中存在重复操作。
本题答案为正确。