埃筛
枚举质数去筛掉它的所有倍数。时间复杂度 \(O(nlogn)\)，可以用 \(bitset\) 优化到 \(O(\frac{1}{64}nlogn)\)。
线性筛
仔细研究埃筛的过程，我们发现每个合数都被筛了多次，考虑优化这个过程使得每个合数都只被它的最小质因子筛掉。
筛法
发布时间 2023-07-08 21:32:42作者: Kun_9
枚举质数去筛掉它的所有倍数。时间复杂度 \(O(nlogn)\)，可以用 \(bitset\) 优化到 \(O(\frac{1}{64}nlogn)\)。
仔细研究埃筛的过程，我们发现每个合数都被筛了多次，考虑优化这个过程使得每个合数都只被它的最小质因子筛掉。