8、下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数。下面说法正确的是( )。

别灰心，再试一次！

【答案】A

【考纲知识点】筛法

【解析】

A. 正确。线性筛法的时间复杂度为 O(n)，因为每个合数只会被其最小质因子标记一次。
B. 错误。
C. 错误。线性筛法和埃拉托色尼筛法的实现思路不同，前者是通过最小质因子标记合数，而后者是通过所有质数的倍数标记合数。