以下关于数论筛法的描述中，正确的是哪一项？

xv821328 单选题共个子题

我们需要求解1~n范围内的素数及相关数论函数，下列说法正确的是？

埃氏筛法的时间复杂度为O(n)，实现简单且能够高效完成素数筛选

线性筛（欧拉筛）每个合数仅会被其最小的质因子标记一次，因此其时间复杂度为O(n)，是目前最优的线性时间素数筛法

数论筛法仅能用于筛选素数，无法同时计算欧拉函数、莫比乌斯函数等附加数论信息

当n取值为10^5时，埃氏筛法与线性筛法的运行效率完全相同，不存在性能差异

正在加载题目数据…

第空

已答 /

子题

第空

提示

该题型需在试卷/作业中作答，单题练习暂不支持

答案解析