判断题 偏易
#19828

在求解所有不大于 n 的素数时,线性筛法(欧拉筛)都应当优先于埃氏筛法使用,因为线性筛法的时间复杂度为O(n),低于埃氏筛法的O(n log log n)。

在求解所有不大于 n 的素数时,线性筛法(欧拉筛)都应当优先于埃氏筛法使用,因为线性筛法的时间复杂度为O(n),低于埃氏筛法的O(n log log n)。

未登录也能判分,登录后才会记录
答案与解析
正确答案:错
解析
分析两种筛法的执行机制:线性筛法通过每个合数仅被其最小质因子标记一次,确保每个数被访问的次数为常数级;埃氏筛法对每个质数的倍数进行标记,存在重复标记同一合数的情况。比较两者操作步骤的数量增长趋势,观察内层循环的触发条件及执行频率,推导各自的时间复杂度表达式。注意算法实现中是否包含冗余操作,以及标记过程的范围和终止条件如何影响总体运算量。