很早之前就了解了min_25筛，当时折腾了两三天魔改各种代码之后存下了一个自用的懒人操作的求积性函数前缀和模板。最近又碰到了些筛法的题，并且重新思考了min_25筛，发现他的前置处理很有意思，而且网上的很多教程写的不明不白，故开一贴写下自己的一些见解（伪教程？）。
这种筛法要从 Problem 10 - Project Euler 说起。在这道题的thread的第五页，Lucy_Hedgehog对于“求n以内质数和”的问题给出了一种亚线性的筛法，复杂度为 $O(n^{0.75})$ （事实上由于素数定理的缘故可以优化至 $O(\frac{n^{0.75}}{lnn})$ ）。而这种筛法的原理正是min_25筛的前置处理过程。
min_25筛
min_25筛是一种亚线性（ $O(\frac{n^{0.75}}{lnn})$ ）求解积性函数的前缀和的方法，只要该积性函数满足“在质数时的表达式为多项式，并且在质数幂次时的值容易求解”，就可以用min_25筛来求解其前缀和（其实有些不具有这样的性质的函数也可以这样求解）。其基本的思路是:首先求解 $\Sigma_{i=1}^{x}f(i)[i为质数]$ 在 $x=\lfloor \frac{n}{1} \rfloor , \lfloor \frac{n}{2} \rfloor , \lfloor \frac{n}{3} \rfloor,…$ 这 $O(\sqrt n)$ 个位置处的取值，然后利用这些值dfs求解即可。这里主要讨论他的前半部分：如何求解 $\Sigma_{i=1}^{x}f(i)[i为质数]$ 在 $x=\lfloor \frac{n}{1} \rfloor , \lfloor \frac{n}{2} \rfloor , \lfloor \frac{n}{3} \rfloor,…$ 这 $O(\sqrt n)$ 个位置处的取值？
如何求解 $\Sigma_{i=1}^{x}f(i)[i为质数]$ ？
网上找到的许多教程都把重点放在“推转移式”，“节省空间的动态规划”上，窃以为既然叫“筛”，那不如从筛法的角度来理解会更合适一点，我们从一个最简单的例子开始入手：求25以内质数的个数。
我们先考虑所有形如 $\lfloor \frac{25}{i} \rfloor$ 的数，这种数只有 $9$ 个，分别是 ${1,2,3,4,5,6,8,12,25}$ (事实上，对于任意的 $n$ ，这种数的个数只有 $2\lfloor \sqrt n \rfloor$ 左右) 。
筛之前我们先把表给列出来（已除去1），其中上半部分表示”现在还有哪些数是质数”，最后那一行是当前数组里的值（筛到目前在x以下的质数还有几个）。
考虑第一个质数 $2$，那么筛 $a[25]$ 时只要用 $a[\lfloor \frac{25}{2} \rfloor]$ 里的数值来筛即可，即：将 $a[ 25 ]$ 一栏下的 $2 * 2 , 2 * 3 , 2 * 4 , … , 2 * 12$ 筛去，同时将 $a[25]$ 中存储的数值 $24$ 减去 $a[12]$ 中存储的数值 $11$ 。
对 $a[12],a[8],…$ 都用 $2$ 筛一遍：
接下来考虑下一个质数 $3$ ，用 $3$ 筛 $a[25]$ 时按照之前的流程也许会出现问题：我用 $a[\lfloor \frac{25}{3} \rfloor]$ 即 $a[8]$ 一栏下的每个数乘以 $3$ ,在 $a[25]$ 下将其划去，可是… $3*2=6$ 已经被划掉了啊？再划掉一次不会出问题么？
回想一下在线性筛时的流程：每个数只会被其最小的质因子筛去一次。事实上，这里也是如此： $6$ 已经在用比 $3$ 更小的质数 $2$ 筛时筛去了。所以我们只需要考虑最小质因子是 $3$ 的数即可。换句话说，此时我们用来删去的集合其实是” $a[8]$ 下那一栏筛剩下的元素” 减去 “ $3$ 之前那个质数（在这里是 $a[2]$ ）下那一栏筛剩下的元素 “ ，$a[25]$ 中存储的元素也相应地减去 $(a[8]-a[2])$ ：
接下来对 $a[12],…$ 用相同操作处理。事实上，由于”如果 $n$ 不是质数，要么 $n$ 最小的质因子一定不大于 $\sqrt n$” ，所以当我们在用素数 $p$ 筛完一轮后（亦即：此时表中已经没有了“拥有比 $p$ 更小的因子的合数”），对于任意小于等于 $p * p$ 的 $t$ , $a[t]$ 中存储的值都已经是 “ $t$ 以下的质数个数” 了，也就是说此时的值都已经是我们想要的真值了。换个角度说，我们只需要使用 $\sqrt n$ 以下的质数即可将我们所需要的信息全部筛出来，同时对于每一轮的筛选也只需要处理满足 $t \geq p*p$ 的 $a[t]$ 即可。附上最终筛完的表：
关于复杂度证明这里就不赘述了，网上铺天盖地的。。。（打latex真的好累啊TAT）
还能干什么？
事实上这种亚线性筛的思想还是很有用的，可以维护质数的任意次幂前缀和，如果再多维护一维之后还可以筛出模一个小质数下不同余数的质数分别有多少个，同时对一些性质不那么好的积性函数只要能用这种筛法维护出他的“质数处函数值前缀和”，就一样可以利用min_25筛的后一部分的转移求出积性函数前缀和。（如有想到再做更新）
