K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
我们需要处理1~n范围内的数论相关问题，以下关于数论筛法的描述正确的是：
埃拉托斯特尼筛法的时间复杂度为O(n log n)，且每个合数仅会被其最小的质因数标记一次
欧拉筛（线性筛法）的时间复杂度为O(n log log n)，仅能用于筛出1~n范围内的所有素数
线性筛法可以在O(n)的时间复杂度内完成，不仅可以筛出素数，还可以同步求解1~n内每个数的最小质因数、欧拉函数等数论信息
筛法仅能用于筛出素数，无法用于求解其他类型的数论函数