本地源文件：docs/math__number-theory__min-25.md

Min_25 筛

定义

从此种筛法的思想方法来说，其又被称为「Extended Eratosthenes Sieve」．

由于其由 Min_25 发明并最早开始使用，故称「Min_25 筛」．

性质

其可以在 𝑂(𝑛34log⁡𝑛)O(n34log⁡n) 或 Θ(𝑛1−𝜖)Θ(n1−ϵ) 的时间复杂度下解决一类 积性函数 的前缀和问题．

要求：𝑓(𝑝)f(p) 是一个关于 𝑝p 可以快速求值的完全积性函数之和（例如多项式）；𝑓(𝑝𝑐)f(pc) 可以快速求值．

记号

• 如无特别说明，本节中所有记为 𝑝p 的变量的取值集合均为全体质数．
• 𝑥/𝑦 :=⌊𝑥𝑦⌋x/y:=⌊xy⌋
• isprime⁡(𝑛) :=[|{𝑑 :𝑑 ∣𝑛}| =2]isprime⁡(n):=[|{d:d∣n}|=2]，即 𝑛n 为质数时其值为 11，否则为 00．
• 𝑝𝑘pk：全体质数中第 𝑘k 小的质数（如：𝑝1 =2,𝑝2 =3p1=2,p2=3）．特别地，令 𝑝0 =1p0=1．
• lpf⁡(𝑛) :=[1 <𝑛]min{𝑝 :𝑝 ∣𝑛} +[1 =𝑛]lpf⁡(n):=[1<n]min{p:p∣n}+[1=n]，即 𝑛n 的最小质因数．特别地，𝑛 =1n=1 时，其值为 11．
• 𝐹prime(𝑛) :=∑2≤𝑝≤𝑛𝑓(𝑝)Fprime(n):=∑2≤p≤nf(p)
• 𝐹𝑘(𝑛) :=∑𝑛𝑖=2[𝑝𝑘 ≤lpf⁡(𝑖)]𝑓(𝑖)Fk(n):=∑i=2n[pk≤lpf⁡(i)]f(i)

解释

观察 𝐹𝑘(𝑛)Fk(n) 的定义，可以发现答案即为 𝐹1(𝑛) +𝑓(1) =𝐹1(𝑛) +1F1(n)+f(1)=F1(n)+1．

考虑如何求出 𝐹𝑘(𝑛)Fk(n)．通过枚举每个 𝑖i 的最小质因子及其次数可以得到递推式：

𝐹𝑘(𝑛)=𝑛∑𝑖=2[𝑝𝑘≤lpf⁡(𝑖)]𝑓(𝑖)=∑𝑘≤𝑖𝑝2𝑖≤𝑛∑𝑐≥1𝑝𝑐𝑖≤𝑛𝑓(𝑝𝑐𝑖)([𝑐>1]+𝐹𝑖+1(𝑛/𝑝𝑐𝑖))+∑𝑘≤𝑖𝑝𝑖≤𝑛𝑓(𝑝𝑖)=∑𝑘≤𝑖𝑝2𝑖≤𝑛∑𝑐≥1𝑝𝑐𝑖≤𝑛𝑓(𝑝𝑐𝑖)([𝑐>1]+𝐹𝑖+1(𝑛/𝑝𝑐𝑖))+𝐹prime(𝑛)−𝐹prime(𝑝𝑘−1)=∑𝑘≤𝑖𝑝2𝑖≤𝑛∑𝑐≥1𝑝𝑐+1𝑖≤𝑛(𝑓(𝑝𝑐𝑖)𝐹𝑖+1(𝑛/𝑝𝑐𝑖)+𝑓(𝑝𝑐+1𝑖))+𝐹prime(𝑛)−𝐹prime(𝑝𝑘−1)Fk(n)=∑i=2n[pk≤lpf⁡(i)]f(i)=∑k≤ipi2≤n∑c≥1pic≤nf(pic)([c>1]+Fi+1(n/pic))+∑k≤ipi≤nf(pi)=∑k≤ipi2≤n∑c≥1pic≤nf(pic)([c>1]+Fi+1(n/pic))+Fprime(n)−Fprime(pk−1)=∑k≤ipi2≤n∑c≥1pic+1≤n(f(pic)Fi+1(n/pic)+f(pic+1))+Fprime(n)−Fprime(pk−1)

最后一步推导基于这样一个事实：对于满足 𝑝𝑐𝑖 ≤𝑛 <𝑝𝑐+1𝑖pic≤n<pic+1 的 𝑐c，有 𝑝𝑐+1𝑖 >𝑛 ⟺ 𝑛/𝑝𝑐𝑖 <𝑝𝑖 <𝑝𝑖+1pic+1>n⟺n/pic<pi<pi+1，故 𝐹𝑖+1(𝑛/𝑝𝑐𝑖) =0Fi+1(n/pic)=0． 其边界值即为 𝐹𝑘(𝑛) =0(𝑝𝑘 >𝑛)Fk(n)=0(pk>n)．

假设现在已经求出了所有的 𝐹prime(𝑛)Fprime(n)，那么有两种方式可以求出所有的 𝐹𝑘(𝑛)Fk(n)：

1. 直接按照递推式计算．
2. 从大到小枚举 𝑝p 转移，仅当 𝑝2 <𝑛p2<n 时转移增加值不为零，故按照递推式后缀和优化即可．

现在考虑如何计算 𝐹prime(𝑛)Fprime(n)． 观察求 𝐹𝑘(𝑛)Fk(n) 的过程，容易发现 𝐹primeFprime 有且仅有 1,2,…,⌊√𝑛⌋,𝑛/√𝑛,…,𝑛/2,𝑛1,2,…,⌊n⌋,n/n,…,n/2,n 这 𝑂(√𝑛)O(n) 处的点值是有用的． 一般情况下，𝑓(𝑝)f(p) 是一个关于 𝑝p 的低次多项式，可以表示为 𝑓(𝑝) =∑𝑎𝑖𝑝𝑐𝑖f(p)=∑aipci． 那么对于每个 𝑝𝑐𝑖pci，其对 𝐹prime(𝑛)Fprime(n) 的贡献即为 𝑎𝑖∑2≤𝑝≤𝑛𝑝𝑐𝑖ai∑2≤p≤npci． 分开考虑每个 𝑝𝑐𝑖pci 的贡献，问题就转变为了：给定 𝑛,𝑠,𝑔(𝑝) =𝑝𝑠n,s,g(p)=ps，对所有的 𝑚 =𝑛/𝑖m=n/i，求 ∑𝑝≤𝑚𝑔(𝑝)∑p≤mg(p)．

注意

𝑔(𝑝) =𝑝𝑠g(p)=ps 是完全积性函数！

于是设 𝐺𝑘(𝑛) :=∑𝑛𝑖=2[𝑝𝑘<lpf⁡(𝑖)∨isprime⁡(𝑖)]𝑔(𝑖)Gk(n):=∑i=2n[pk<lpf⁡(i)∨isprime⁡(i)]g(i)，即埃筛第 𝑘k 轮筛完后剩下的数的 𝑔g 值之和． 对于一个合数 𝑥 ≤𝑛x≤n，必定有 lpf⁡(𝑥) ≤√𝑥 ≤√𝑛lpf⁡(x)≤x≤n．设 𝑝ℓ(𝑛)pℓ(n) 为不大于 √𝑛n 的最大质数，则 ∑2≤𝑝≤𝑛𝑔(𝑝) =𝐺ℓ(𝑛)(𝑛)∑2≤p≤ng(p)=Gℓ(n)(n)，即在埃筛进行 ℓℓ 轮之后剩下的均为质数． 考虑 𝐺G 的边界值，显然为 𝐺0(𝑛) =∑𝑛𝑖=2𝑔(𝑖)G0(n)=∑i=2ng(i)．（还记得吗？特别约定了 𝑝0 =1p0=1） 对于转移，考虑埃筛的过程，分开讨论每部分的贡献，有：

1. 对于 𝑛 <𝑝2𝑘n<pk2 的部分，𝐺G 值不变，即 𝐺𝑘(𝑛) =𝐺𝑘−1(𝑛)Gk(n)=Gk−1(n)．
2. 对于 𝑝2𝑘 ≤𝑛pk2≤n 的部分，被筛掉的数必有质因子 𝑝𝑘pk，即 −𝑔(𝑝𝑘)𝐺𝑘−1(𝑛/𝑝𝑘)−g(pk)Gk−1(n/pk)．
3. 对于第二部分，由于 𝑝2𝑘 ≤𝑛 ⟺ 𝑝𝑘 ≤𝑛/𝑝𝑘pk2≤n⟺pk≤n/pk，满足 lpf⁡(𝑖) <𝑝𝑘lpf⁡(i)<pk 的 𝑖i 会被额外减去．这部分应当加回来，即 𝑔(𝑝𝑘)𝐺𝑘−1(𝑝𝑘−1)g(pk)Gk−1(pk−1)．

则有：

𝐺𝑘(𝑛)=𝐺𝑘−1(𝑛)−[𝑝2𝑘≤𝑛]𝑔(𝑝𝑘)(𝐺𝑘−1(𝑛/𝑝𝑘)−𝐺𝑘−1(𝑝𝑘−1))Gk(n)=Gk−1(n)−[pk2≤n]g(pk)(Gk−1(n/pk)−Gk−1(pk−1))

复杂度分析

对于 𝐹𝑘(𝑛)Fk(n) 的计算，其第一种方法的时间复杂度被证明为 𝑂(𝑛1−𝜖)O(n1−ϵ)（见朱震霆集训队论文 《一些特殊的数论函数求和问题》 2.3）； 对于第二种方法，其本质即为洲阁筛的第二部分，在任之洲论文 《积性函数求和的几种方法》 中也有提及（6.5.4），其时间复杂度被证明为 𝑂(𝑛34log⁡𝑛)O(n34log⁡n)．

对于 𝐹prime(𝑛)Fprime(n) 的计算，事实上，其实现与洲阁筛第一部分是相同的． 考虑对于每个 𝑚 =𝑛/𝑖m=n/i，只有在枚举满足 𝑝2𝑘 ≤𝑚pk2≤m 的 𝑝𝑘pk 转移时会对时间复杂度产生贡献，则时间复杂度可估计为：

𝑇(𝑛)=∑𝑖2≤𝑛𝑂(𝜋(√𝑖))+∑𝑖2≤𝑛𝑂(𝜋(√𝑛𝑖))=∑𝑖2≤𝑛𝑂(√𝑖ln⁡√𝑖)+∑𝑖2≤𝑛𝑂(√𝑛𝑖ln⁡√𝑛𝑖)=𝑂(∫√𝑛1√𝑛𝑥log⁡√𝑛𝑥d𝑥)=𝑂(𝑛34log⁡𝑛)T(n)=∑i2≤nO(π(i))+∑i2≤nO(π(ni))=∑i2≤nO(iln⁡i)+∑i2≤nO(niln⁡ni)=O(∫1nnxlog⁡nxdx)=O(n34log⁡n)

对于空间复杂度，可以发现不论是 𝐹𝑘Fk 还是 𝐹primeFprime，其均只在 𝑛/𝑖n/i 处取有效点值，共 𝑂(√𝑛)O(n) 个，仅记录有效值即可将空间复杂度优化至 𝑂(√𝑛)O(n)．

首先，通过一次数论分块可以得到所有的有效值，用一个大小为 𝑂(√𝑛)O(n) 的数组 lislis 记录．对于有效值 𝑣v，记 id(𝑣)id(v) 为 𝑣v 在 lislis 中的下标，易得：对于所有有效值 𝑣v，id(𝑣) ≤√𝑛id(v)≤n．

然后分开考虑小于等于 √𝑛n 的有效值和大于 √𝑛n 的有效值：对于小于等于 √𝑛n 的有效值 𝑣v，用一个数组 lele 记录其 id(𝑣)id(v)，即 le𝑣 =id(𝑣)lev=id(v)；对于大于 √𝑛n 的有效值 𝑣v，用一个数组 gege 记录 id(𝑣)id(v)，由于 𝑣v 过大所以借助 𝑣′ =𝑛/𝑣 <√𝑛v′=n/v<n 记录 id(𝑣)id(v)，即 ge𝑣′ =id(𝑣)gev′=id(v)．

这样，就可以使用两个大小为 𝑂(√𝑛)O(n) 的数组记录所有有效值的 idid 并 𝑂(1)O(1) 查询．在计算 𝐹𝑘Fk 或 𝐹primeFprime 时，使用有效值的 idid 代替有效值作为下标，即可将空间复杂度优化至 𝑂(√𝑛)O(n)．

过程

对于 𝐹𝑘(𝑛)Fk(n) 的计算，我们实现时一般选择实现难度较低的第一种方法，其在数据规模较小时往往比第二种方法的表现要好；

对于 𝐹prime(𝑛)Fprime(n) 的计算，直接按递推式实现即可．

对于 𝑝2𝑘 ≤𝑛pk2≤n，可以用线性筛预处理出 𝑠𝑘 :=𝐹prime(𝑝𝑘)sk:=Fprime(pk) 来替代 𝐹𝑘Fk 递推式中的 𝐹prime(𝑝𝑘−1)Fprime(pk−1)． 相应地，𝐺G 递推式中的 𝐺𝑘−1(𝑝𝑘−1) =∑𝑘−1𝑖=1𝑔(𝑝𝑖)Gk−1(pk−1)=∑i=1k−1g(pi) 也可以用此方法预处理．

用 Extended Eratosthenes Sieve 求 积性函数 𝑓f 的前缀和时，应当明确以下几点：

• 如何快速（一般是线性时间复杂度）筛出前 √𝑛n 个 𝑓f 值；
• 𝑓(𝑝)f(p) 的多项式表示；
• 如何快速求出 𝑓(𝑝𝑐)f(pc)．

明确上述几点之后按顺序实现以下几部分即可：

1. 筛出 [1,√𝑛][1,n] 内的质数与前 √𝑛n 个 𝑓f 值；
2. 对 𝑓(𝑝)f(p) 多项式表示中的每一项筛出对应的 𝐺G，合并得到 𝐹primeFprime 的所有 𝑂(√𝑛)O(n) 个有用点值；
3. 按照 𝐹𝑘Fk 的递推式实现递归，求出 𝐹1(𝑛)F1(n)．

例题

Luogu P4213【模板】杜教筛

求 𝑛∑𝑖=1𝜑(𝑖)∑i=1nφ(i) 和 𝑛∑𝑖=1𝜇(𝑖)∑i=1nμ(i)．

解答

对于求 𝜑(𝑖)φ(i) 的前缀和，首先易知 𝑓(𝑝) =𝑝 −1f(p)=p−1．对于 𝑓(𝑝)f(p) 的一次项 (𝑝)(p)，有 𝑔(𝑝) =𝑝,𝐺0(𝑛) =∑𝑛𝑖=2𝑔(𝑖) =(𝑛+2)(𝑛−1)2g(p)=p,G0(n)=∑i=2ng(i)=(n+2)(n−1)2；对于 𝑓(𝑝)f(p) 的常数项 ( −1)(−1)，有 𝑔(𝑝) = −1,𝐺0(𝑛) =∑𝑛𝑖=2𝑔(𝑖) = −𝑛 +1g(p)=−1,G0(n)=∑i=2ng(i)=−n+1．筛两次加起来即可得到 𝐹primeFprime 的所有 𝑂(√𝑛)O(n) 个所需点值．

对于求 𝜇(𝑖)μ(i) 的前缀和，易知 𝑓(𝑝) = −1f(p)=−1．则 𝑔(𝑝) = −1,𝐺0(𝑛) =∑𝑛𝑖=2𝑔(𝑖) = −𝑛 +1g(p)=−1,G0(n)=∑i=2ng(i)=−n+1．直接筛即可得到 𝐹primeFprime 的所有 𝑂(√𝑛)O(n) 个所需点值．

LOJ 6053 简单的函数

给定 𝑓(𝑛)f(n)：

𝑓(𝑛)=⎧{ {⎨{ {⎩1𝑛=1𝑝xor⁡𝑐𝑛=𝑝𝑐𝑓(𝑎)𝑓(𝑏)𝑛=𝑎𝑏∧𝑎⟂𝑏f(n)={1n=1pxor⁡cn=pcf(a)f(b)n=ab∧a⟂b

求 𝑛∑𝑖=1𝑓(𝑖)∑i=1nf(i)．

解答

易知 𝑓(𝑝) =𝑝 −1 +2[𝑝 =2]f(p)=p−1+2[p=2]．则按照筛 𝜑φ 的方法筛，对 22 讨论一下即可．

参考代码

---|---

* * *

> __本页面最近更新： 2026/2/8 14:42:40，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/math/number-theory/min-25.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/math/number-theory/min-25.md "edit.link.title")
>  __本页面贡献者：[Marcythm](https://github.com/Marcythm), [Tiphereth-A](https://github.com/Tiphereth-A), [Xeonacid](https://github.com/Xeonacid), [MegaOwIer](https://github.com/MegaOwIer), [StudyingFather](https://github.com/StudyingFather), [CSPNOIP](https://github.com/CSPNOIP), [Enter-tainer](https://github.com/Enter-tainer), [HeRaNO](https://github.com/HeRaNO), [aofall](https://github.com/aofall), [Backl1ght](https://github.com/Backl1ght), [c-forrest](https://github.com/c-forrest), [CoelacanthusHex](https://github.com/CoelacanthusHex), [Enoch-xm](https://github.com/Enoch-xm), [Great-designer](https://github.com/Great-designer), [Haohu Shen](mailto:haohu.shen@ucalgary.ca), [iamtwz](https://github.com/iamtwz), [Ir1d](https://github.com/Ir1d), [kenlig](https://github.com/kenlig), [Konano](https://github.com/Konano), [ksyx](https://github.com/ksyx), [Persdre](https://github.com/Persdre), [Revltalize](https://github.com/Revltalize), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [shuzhouliu](https://github.com/shuzhouliu), [ZnPdCo](https://github.com/ZnPdCo)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用