K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
我们需要求解1~n范围内的素数及相关数论函数，下列说法正确的是？
埃氏筛法的时间复杂度为O(n)，实现简单且能够高效完成素数筛选
线性筛（欧拉筛）每个合数仅会被其最小的质因子标记一次，因此其时间复杂度为O(n)，是目前最优的线性时间素数筛法
数论筛法仅能用于筛选素数，无法同时计算欧拉函数、莫比乌斯函数等附加数论信息
当n取值为10^5时，埃氏筛法与线性筛法的运行效率完全相同，不存在性能差异