筛法
素数筛法
引入
如果我们想要知道小于等于 𝑛n
有多少个素数呢？
一个自然的想法是对于小于等于 𝑛n 的每个数进行一次质数检验．这种暴力的做法显然不能达到最优复杂度．
埃拉托斯特尼筛法
过程
考虑这样一件事情：对于任意一个大于 11 的正整数 𝑛n，那么它的 𝑥x 倍就是合数（𝑥 >1x>1）．利用这个结论，我们可以避免很多次不必要的检测．
如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了．
实现
C++Python
---|---
---|---
以上为 Eratosthenes 筛法 （埃拉托斯特尼筛法，简称埃氏筛法），时间复杂度是 𝑂(𝑛loglog𝑛)O(nloglogn)．
证明
现在我们就来看看推导过程：
如果每一次对数组的操作花费 1 个单位时间，则时间复杂度为：
𝑂(𝜋(𝑛)∑𝑘=1𝑛𝑝𝑘)=𝑂(𝑛𝜋(𝑛)∑𝑘=11𝑝𝑘)O(∑k=1π(n)npk)=O(n∑k=1π(n)1pk)
其中 𝑝𝑘pk 表示第 𝑘k 小的素数，𝜋(𝑛)π(n) 表示 ≤𝑛≤n 的素数个数．∑𝜋(𝑛)𝑘=1∑k=1π(n) 表示第一层 for 循环，其中累加上界 𝜋(𝑛)π(n) 为 if (prime[i]) 进入 true 分支的次数；𝑛𝑝𝑘npk 表示第二层 for 循环的执行次数．
根据 Mertens 第二定理，存在常数 𝐵1B1 使得：
𝜋(𝑛)∑𝑘=11𝑝𝑘=loglog𝑛+𝐵1+𝑂(1log𝑛)∑k=1π(n)1pk=loglogn+B1+O(1logn)
所以 Eratosthenes 筛法 的时间复杂度为 𝑂(𝑛loglog𝑛)O(nloglogn)．接下来我们证明 Mertens 第二定理的弱化版本 ∑𝑘≤𝜋(𝑛)1/𝑝𝑘 =𝑂(loglog𝑛)∑k≤π(n)1/pk=O(loglogn)：
根据 𝜋(𝑛) =Θ(𝑛/log𝑛)π(n)=Θ(n/logn)，可知第 𝑛n 个素数的大小为 Θ(𝑛log𝑛)Θ(nlogn)．于是就有
𝜋(𝑛)∑𝑘=11𝑝𝑘=𝑂(𝜋(𝑛)∑𝑘=21𝑘log𝑘)=𝑂(∫𝜋(𝑛)2d𝑥𝑥log𝑥)=𝑂(loglog𝜋(𝑛))=𝑂(loglog𝑛)∑k=1π(n)1pk=O(∑k=2π(n)1klogk)=O(∫2π(n)dxxlogx)=O(loglogπ(n))=O(loglogn)
当然，上面的做法效率仍然不够高效，应用下面几种方法可以稍微提高算法的执行效率．
筛至平方根
显然，要找到直到 𝑛n 为止的所有素数，仅对不超过 √𝑛n 的素数进行筛选就足够了．
C++Python
---|---
---|---
这种优化不会影响渐近时间复杂度，实际上重复以上证明，我们将得到 𝑛lnln√𝑛 +𝑜(𝑛)nlnlnn+o(n)，根据对数的性质，它们的渐近相同，但操作次数会明显减少．
只筛奇数
因为除 2 以外的偶数都是合数，所以我们可以直接跳过它们，只用关心奇数就好．
首先，这样做能让我们内存需求减半；其次，所需的操作大约也减半．
减少内存的占用
我们注意到筛选时只需要 bool 类型的数组．bool 数组的一个元素一般占用 11 字节（即 88 比特），但是存储一个布尔值只需要 11 个比特就足够了．
我们可以使用 位操作 的相关知识，将每个布尔值压到一个比特位中，这样我们仅需使用 𝑛n 比特（即 𝑛8n8 字节）而非 𝑛n 字节，可以显著减少内存占用．这种方式被称为「位级压缩」．
值得一提的是，存在自动执行位级压缩的数据结构，如 C++ 中的 vector<bool> 和 bitset<>．
另外，vector<bool> 和 bitset<> 对程序有常数优化，时间复杂度 𝑂(𝑛loglog𝑛)O(nloglogn) 的埃氏筛在使用 bitset<> 或 vector<bool> 优化后，性能甚至超过时间复杂度 𝑂(𝑛)O(n) 的欧拉筛．
参见 bitset: 与埃氏筛结合．
分块筛选
由优化「筛至平方根」可知，不需要一直保留整个 is_prime[1...n] 数组．为了进行筛选，只保留到 √𝑛n 的素数就足够了，即 prime[1...sqrt(n)]．并将整个范围分成块，每个块分别进行筛选．这样，我们就不必同时在内存中保留多个块，而且 CPU 可以更好地处理缓存．
设 𝑠s 是一个常数，它决定了块的大小，那么我们就有了 ⌈𝑛𝑠⌉⌈ns⌉ 个块，而块 𝑘k(𝑘 =0…⌊𝑛𝑠⌋k=0…⌊ns⌋) 包含了区间 [𝑘𝑠,𝑘𝑠 +𝑠 −1][ks,ks+s−1] 中的数字．我们可以依次处理块，也就是说，对于每个块 𝑘k，我们将遍历所有质数（从 11 到 √𝑛n）并使用它们进行筛选．
值得注意的是，我们在处理第一个数字时需要稍微修改一下策略：首先，应保留 [1,√𝑛][1,n] 中的所有的质数；第二，数字 00 和 11 应该标记为非素数．在处理最后一个块时，不应该忘记最后一个数字 𝑛n 并不一定位于块的末尾．
以下实现使用块筛选来计算小于等于 𝑛n 的质数数量．
实现
---|---
分块筛法的渐近时间复杂度与埃氏筛法是一样的（除非块非常小），但是所需的内存将缩小为 𝑂(√𝑛 +𝑆)O(n+S)，并且有更好的缓存结果． 另一方面，对于每一对块和区间 [1,√𝑛][1,n] 中的素数都要进行除法，而对于较小的块来说，这种情况要糟糕得多． 因此，在选择常数 𝑆S 时要保持平衡．
块大小 𝑆S 取 104104 到 105105 之间，可以获得最佳的速度．
### 线性筛法
埃氏筛法仍有优化空间，它会将一个合数重复多次标记．有没有什么办法省掉无意义的步骤呢？答案是肯定的．
如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 𝑂(𝑛)O(n) 了．
实现
C++Python
---|---
---|---
上面的这种 **线性筛法** 也称为 **Euler 筛法** （欧拉筛法）．
Note
注意到筛法求素数的同时也得到了每个数的最小质因子．
## 筛法求欧拉函数
注意到在线性筛中，每一个合数都是被最小的质因子筛掉．比如设 𝑝1p1 是 𝑛n 的最小质因子，𝑛′ =𝑛𝑝1n′=np1，那么线性筛的过程中 𝑛n 通过 𝑛′ ×𝑝1n′×p1 筛掉．
观察线性筛的过程，我们还需要处理两个部分，下面对 𝑛′mod𝑝1n′modp1 分情况讨论．
如果 𝑛′mod𝑝1 =0n′modp1=0，那么 𝑛′n′ 包含了 𝑛n 的所有质因子．
𝜑(𝑛)=𝑛×𝑠∏𝑖=1𝑝𝑖−1𝑝𝑖=𝑝1×𝑛′×𝑠∏𝑖=1𝑝𝑖−1𝑝𝑖=𝑝1×𝜑(𝑛′)φ(n)=n×∏i=1spi−1pi=p1×n′×∏i=1spi−1pi=p1×φ(n′)
那如果 𝑛′mod𝑝1 ≠0n′modp1≠0 呢，这时 𝑛′n′ 和 𝑝1p1 是互质的，根据欧拉函数性质，我们有：
𝜑(𝑛)=𝜑(𝑝1)×𝜑(𝑛′)=(𝑝1−1)×𝜑(𝑛′)φ(n)=φ(p1)×φ(n′)=(p1−1)×φ(n′)
### 实现
C++Python
---|---
---|---
## 筛法求莫比乌斯函数
### 定义
根据莫比乌斯函数的定义，设 𝑛n 是一个合数，𝑝1p1 是 𝑛n 的最小质因子，𝑛′ =𝑛𝑝1n′=np1，有：
𝜇(𝑛)=⎧{ {⎨{ {⎩0𝑛′mod𝑝1=0−𝜇(𝑛′)otherwiseμ(n)={0n′modp1=0−μ(n′)otherwise
若 𝑛n 是质数，有 𝜇(𝑛) = −1μ(n)=−1．
### 实现
C++Python
---|---
---|---
## 筛法求约数个数
用 𝑑𝑖di 表示 𝑖i 的约数个数，𝑛𝑢𝑚𝑖numi 表示 𝑖i 的最小质因子出现次数．
### 约数个数定理
定理：若 𝑛 =∏𝑚𝑖=1𝑝𝑐𝑖𝑖n=∏i=1mpici 则 𝑑𝑖 =∏𝑚𝑖=1(𝑐𝑖 +1)di=∏i=1m(ci+1)．
证明：我们知道 𝑝𝑐𝑖𝑖pici 的约数有 𝑝0𝑖,𝑝1𝑖,…,𝑝𝑐𝑖𝑖pi0,pi1,…,pici 共 𝑐𝑖 +1ci+1 个，根据乘法原理，𝑛n 的约数个数就是 ∏𝑚𝑖=1(𝑐𝑖 +1)∏i=1m(ci+1)．
### 实现
因为 𝑑𝑖di 是积性函数，所以可以使用线性筛．
在这里简单介绍一下线性筛实现原理．
1. 当 𝑖i 为质数时，𝑛𝑢𝑚𝑖 ←1,𝑑𝑖 ←2numi←1,di←2，同时设 𝑞 =⌊𝑖𝑝⌋q=⌊ip⌋，其中 𝑝p 为 𝑖i 的最小质因子．
2. 当 𝑝p 为 𝑞q 的质因子时，𝑛𝑢𝑚𝑖 ←𝑛𝑢𝑚𝑞 +1,𝑑𝑖 ←𝑑𝑞𝑛𝑢𝑚𝑖 ×(𝑛𝑢𝑚𝑖 +1)numi←numq+1,di←dqnumi×(numi+1)．
3. 当 𝑝,𝑞p,q 互质时，𝑛𝑢𝑚𝑖 ←1,𝑑𝑖 ←𝑑𝑞 ×(𝑛𝑢𝑚𝑖 +1)numi←1,di←dq×(numi+1)．
C++Python
---|---
---|---
## 筛法求约数和
𝑓𝑖fi 表示 𝑖i 的约数和，𝑔𝑖gi 表示 𝑖i 的最小质因子的 𝑝0 +𝑝1 +𝑝2 +…𝑝𝑘p0+p1+p2+…pk.
### 实现
C++Python
---|---
---|---
## 一般的积性函数
假如一个 [积性函数](../basic/#积性函数) 𝑓f 满足：对于任意质数 𝑝p 和正整数 𝑘k，可以在关于 𝑘k 的低次多项式时间内计算 𝑓(𝑝𝑘)f(pk)，那么可以在 𝑂(𝑛)O(n) 时间内筛出 𝑓(1),𝑓(2),…,𝑓(𝑛)f(1),f(2),…,f(n) 的值．
设合数 𝑛n 的质因子分解是 ∏𝑘𝑖=1𝑝𝛼𝑖𝑖∏i=1kpiαi，其中 𝑝1 <𝑝2 <⋯ <𝑝𝑘p1<p2<⋯<pk 为质数，我们在线性筛中记录 𝑔𝑛 =𝑝𝛼11gn=p1α1，假如 𝑛n 被 𝑥 ⋅𝑝x⋅p 筛掉（𝑝p 是质数），那么 𝑔g 满足如下递推式：
𝑔𝑛=⎧{ {⎨{ {⎩𝑔𝑥⋅𝑝𝑥mod𝑝=0𝑝otherwisegn={gx⋅pxmodp=0potherwise
假如 𝑛 =𝑔𝑛n=gn，说明 𝑛n 就是某个质数的次幂，可以 𝑂(1)O(1) 计算 𝑓(𝑛)f(n)；否则，𝑓(𝑛) =𝑓(𝑛𝑔𝑛) ⋅𝑓(𝑔𝑛)f(n)=f(ngn)⋅f(gn)．
**本节部分内容译自博文[Решето Эратосфена](http://e-maxx.ru/algo/eratosthenes_sieve) 与其英文翻译版 [Sieve of Eratosthenes](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html)．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．**
* * *
> __本页面最近更新： 2026/1/27 12:26:08，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/math/number-theory/sieve.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/math/number-theory/sieve.md "edit.link.title")
> __本页面贡献者：[Ir1d](https://github.com/Ir1d), [StudyingFather](https://github.com/StudyingFather), [Tiphereth-A](https://github.com/Tiphereth-A), [Enter-tainer](https://github.com/Enter-tainer), [LJFYC007](https://github.com/LJFYC007), [Xeonacid](https://github.com/Xeonacid), [H-J-Granger](https://github.com/H-J-Granger), [iamtwz](https://github.com/iamtwz), [mgt](mailto:i@margatroid.xyz), [shuzhouliu](https://github.com/shuzhouliu), [CCXXXI](https://github.com/CCXXXI), [countercurrent-time](https://github.com/countercurrent-time), [NachtgeistW](https://github.com/NachtgeistW), [c-forrest](https://github.com/c-forrest), [Early0v0](https://github.com/Early0v0), [HeRaNO](https://github.com/HeRaNO), [MegaOwIer](https://github.com/MegaOwIer), [Peanut-Tang](https://github.com/Peanut-Tang), [YOYO-UIAT](https://github.com/YOYO-UIAT), [AngelKitty](https://github.com/AngelKitty), [cjsoft](https://github.com/cjsoft), [diauweb](https://github.com/diauweb), [ezoixx130](https://github.com/ezoixx130), [GekkaSaori](https://github.com/GekkaSaori), [Great-designer](https://github.com/Great-designer), [greyqz](https://github.com/greyqz), [Konano](https://github.com/Konano), [LovelyBuggies](https://github.com/LovelyBuggies), [Makkiy](https://github.com/Makkiy), [minghu6](https://github.com/minghu6), [Mr-Python-in-China](https://github.com/Mr-Python-in-China), [P-Y-Y](https://github.com/P-Y-Y), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [sshwy](https://github.com/sshwy), [Suyun514](mailto:suyun514@qq.com), [TravorLZH](https://github.com/TravorLZH), [weilycoder](https://github.com/weilycoder), [weiyong1024](https://github.com/weiyong1024), [1804040636](https://github.com/1804040636), [383494](https://github.com/383494), [aofall](https://github.com/aofall), [CoelacanthusHex](https://github.com/CoelacanthusHex), [cubeheadsun](https://github.com/cubeheadsun), [frank-xjh](https://github.com/frank-xjh), [GavinZhengOI](https://github.com/GavinZhengOI), [Gesrua](https://github.com/Gesrua), [hhc0001](https://github.com/hhc0001), [hqztrue](https://github.com/hqztrue), [ImpleLee](https://github.com/ImpleLee), [inkydragon](https://github.com/inkydragon), [ksyx](https://github.com/ksyx), [kxccc](https://github.com/kxccc), [luojiny1](https://github.com/luojiny1), [Lutra-Fs](https://github.com/Lutra-Fs), [lychees](https://github.com/lychees), [Marcythm](https://github.com/Marcythm), [Menci](https://github.com/Menci), [opsiff](https://github.com/opsiff), [partychicken](https://github.com/partychicken), [PerfectPan](https://github.com/PerfectPan), [Persdre](https://github.com/Persdre), [shawlleyw](https://github.com/shawlleyw), [StableAgOH](https://github.com/StableAgOH), [Steaunk](https://github.com/Steaunk), [SukkaW](https://github.com/SukkaW), [sunruisjtu2020](https://github.com/sunruisjtu2020), [TianKong-y](https://github.com/TianKong-y), [TOMWT-qwq](https://github.com/TOMWT-qwq), [TrisolarisHD](mailto:orzcyand1317@gmail.com), [untitledunrevised](https://github.com/untitledunrevised), [WAAutoMaton](https://github.com/WAAutoMaton), [WineChord](https://github.com/WineChord), [wkywkyQAQ](https://github.com/wkywkyQAQ), [wood3](https://github.com/wood3), [YanWQ-monad](https://github.com/YanWQ-monad), [Yisheng Gong](mailto:yisheng_gong@onmail.com), [zhouyuyang2002](https://github.com/zhouyuyang2002), [ZnPdCo](https://github.com/ZnPdCo), [代建杉](mailto:wood3s@foxmail.com)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用