OI Wiki-Alter 筛法
筛法 筛法 目录
素数筛法
埃拉托斯特尼筛法
筛至平方根
只筛奇数
减少内存的占用
分块筛选
线性筛法
筛法求欧拉函数
筛法求莫比乌斯函数
筛法求约数个数
约数个数定理
筛法求约数和
一般的积性函数
如果我们想要知道小于等于 有多少个素数呢?
一个自然的想法是对于小于等于 的每个数进行一次质数检验.这种暴力的做法显然不能达到最优复杂度.
考虑这样一件事情:对于任意一个大于 的正整数 ,那么它的 倍就是合数().利用这个结论,我们可以避免很多次不必要的检测.
如果我们从小到大考虑每个数,然后同时把当前这个数的所有(比自己大的)倍数记为合数,那么运行结束的时候没有被标记的数就是素数了.