假如碰到一道题，询问在[ $l,r$ ]区间( $r$ $\leq$ $n$ )中有多少个质数，该怎么处理？显然，这个问题与“小于等于 $n$ 的质数有多少个”是等价的。我们知道，如果 $n$ 的范围在 $1e7$ 以内，那可以通过线性筛法筛出答案，复杂度 $O(n)$ ,甚至当 $n$ 更小时，用埃拉托斯特尼筛就足以给出答案，但是当 $n$ 更大时该如何处理呢？比如 $1e9$ , $1e10$ 甚至 $1e11$ ？（相关题目：HDU 5901（2016沈阳网络赛），CF 665F）Meissel-Lehmer算法正是一种用于处理这种问题的算法。
先给出原论文链接：http://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777285-5/S0025-5718-1985-0777285-5.pdf 网上关于ML算法的模板不少，但几乎找不到什么讲原理的文章，所以就去找了相关论文，粗略的读了一下，写出来与大家分享（希望没有理解错原理23333）不足之处望指出，持续补充更新~
(接下来提到的都是经Jeffrey Lagarias, Victor Miller 和 Andrew Odlyzko改良后的Meissel-Lehmer算法的思路)
为方便起见，我们用符号 $\pi(x)$ 代表“不大于$x$的质数的个数”，与以往的“筛选掉合数”的思路不同，Meissel-Lehmer算法的思路比较清奇，他考虑的是：不大于 $x$ 的质数可以分成两部分，一部分是前 $a$ 个质数( $p_1,p_2,…,p_a$ )，另一部分是剩下的质数。假设剩下的质数有 $t$ 个，那么在同时算出 $a$ 和 $t$ 的情况下，就得到了 $\pi(x)$ 的值：$a+t$。
那么我们现在换一个思路来考虑“质数”这个概念。众所周知，质数是”除了1以外因子只有其本身”的数，而对于每一个有限的自然数（除1以外），必定可以唯一的分解为有限个质数的乘积（唯一分解定理）。所以换言之，如果用“分解的质因子个数”来对自然数分类是一种可行、合法的分类方式，而质数集体正是这其中“恰有一个质因子”这一类的全体。那么如果我们再加入一个条件，即：恰有一个质因子，且这个质因子是大于前a个质数的，并且这个数是不大于x的。这样表示的不就是( $p_a,x$ ]中的质数全体了吗？我们把它的个数记为 $P_1(x,a)$ ，那么我们现在有了一个有意思的等式：$P_1(x,a)+a=\pi(x)$ 。
相似的，我们用 $P_k(x,a)$ 表示：“不大于 $x$ ，且恰有 $k$ 个质因子（每个质因子均大于 $p_a$ ）的数”的个数，那么如果我们把 $k=0,1,2,…$ 的情况全部加起来，得到的岂不就是…所有不大于 $x$ 的自然数的个数？好吧其实并不是，我们得到的将是“不大于 $x$ 的数中，分解后不含有 $p_1,p_2,…,p_a$ 这些质因子的数”的个数，不妨再给他一个记号: $\phi (x,a)$ 。那么现在我们又有了一个有意思的等式： $\phi(x,a)=\sum_{k=0}^{\infty}P_k(x,a)$ ，其中 $P_0(x,a)=1$ ，代表1这个自然数。
整理一下，我们目前有三个记号，分别是：
$\pi(x)$ ：不大于 $x$ 的质数的个数
$P_k(x,a)$ ：不大于 $x$ ，且恰有 $k$ 个质因子（每个质因子均大于 $p_a$ ）的数的个数
$\phi(x,a)$ ：不大于 $x$ 的数中，分解后不含前 $a$ 个质数的数的个数
并且我们有两个等式：
$P_1(x,a)+a=\pi(x)$ $\qquad\qquad\qquad$ $(1)$
$\phi(x,a)=\sum_{k=0}^{\infty}P_k(x,a)$ $\ \qquad\qquad$ $(2)$
我们的目标是计算出 $\pi(x)$ ,而由 $(1)$ 式可知，我们只需要知道$a$和 $P_1(x,a)$ 即可。显然，这里的$a$是可以任意取的（$a \leq \pi(x)$）,而$P_1(x,a)$ 的求法由 $(2)$ 式也许可以计算。但由于 $(2)$ 式中含有一个无穷级数，求法似乎也不那么显然…那怎么办…凉了呀…
然而仔细一想，这个无穷级数好像是骗人的？他一定只有有限项不是0！比如说比不大于8的数中，最多最多只有3个质因子（ $8=2*2*2$ ），不大于27、且分解后不含第一个质数2的数最多最多只有3个质因子（$27=3*3*3$）…那么我们是不是可以取合适的$a$，使得这个无穷级数只有前面2或3项不是0，剩下的都是0？这样不就好处理多了吗！不妨取 $a=\pi(x^{1/3})$，这样的话就只有$P_{0}(x,a),P_{1}(x,a),p_{2}(x,a)$ 非零，剩下的全是零了！
那么整理一下，现在我们的式子已经化简为了：
$$\pi(x)=a+\phi(x,a)-P_{0}(x,a)-P_{2}(x,a)$$
由于$P_{0}(x,a)=1$,所以等价于：
$$\pi(x)=a+\phi(x,a)-1-P_{2}(x,a)$$
其中$a=\pi(x^{1/3})$ 。
那么接下来就是考虑如何求解 $\phi(x,a)$ 和 $P_{2}(x,a)$ 的问题了。
首先我们考虑$P_{2}(x,a)$。由定义可知：
$$
P_{2}(x,a)=|\lbrace n| n=p_bp_c,a<b\le c \rbrace |\\
\qquad\qquad\qquad\qquad =\sum_{b=a+1}^{\pi ( x^{1/2} )}
{\left| \lbrace n| n=p_bp_c,b\le c\le \pi ( \frac{x}{P_b} )\rbrace \right|}\\
\qquad\qquad=\sum_{b=a+1}^{\pi ( x^{1/2} )}{\left( \pi \left( \frac{x}{p_b} \right) -b+1 \right)}\\
\qquad\qquad=\sum_{b=a+1}^{\pi ( x^{1/2} )}{\pi \left(\frac{x}{p_b} \right)}+\frac{a\left( a-1 \right)}{2}-\frac{\pi \left( x^{\frac{1}{2}} \right) \left( \pi \left( x^{\frac{1}{2}} \right) -1 \right)}{2}
$$
观察后不难发现，这个式子中所有需求的变量只有 $\pi(t)$,并且所有的$t$都是小于$x^{2/3}$ 次的！那么接下来我们要做的就是把我们所需要的、小于$x^{2/3}$ 的$t$的 $\pi(t)$ 的值全部算出来。
首先，我们将 $[1,x^{2/3}]$ 按 $\lfloor x^{1/3} \rfloor$的长度进行切分（接下来记 $\lfloor x^{1/3} \rfloor$ 为$N$），第$j$个区间记为 $\left[ \left( j-1 \right) N+1,jN \right]$ ，那么除了最后一个区间的长度有可能比$N$小以外，其余每个区间长度均为$N$，一共有至多 $x^{1/3}+1$ 个区间。对于第一个区间，我们可以轻松地用线性筛把其中的质数筛出来，即：存下小于等于 $x^{1/3}$ 的所有质数。那么接下来对每一个区间，由于所有区间中的数最大也不会超过$x^{2/3}$，所以假如该区间中的数是合数，则必有一个因子是小于$x^{1/3}$ 的，因此，假如我们已经得到了上一个区间末尾的 $\pi((j-1)N)$ 的值，我们就可以用我们存下的质数表，利用线性筛的原理在线性时间复杂度内筛出某个区间的所有质数，同时也就得到了该区间每一个数$n$的 $\pi(n)$ 值（其中储存末尾的 $\pi(jN)$ 为下一个区间使用），那么接下来要做的事就是把每个区间中形如 $\pi\left(\frac{x}{p_b}\right)$ 的值都加起来，以便于求解 $\sum_{b=a+1}^{\pi ( x^{1/2} )}$ 。
对于每一个在 $[x^{1/2},x^{2/3}]$ 之中，且满足 $\frac{x}{p}$ 在第$j$个区间内的质数p，他满足：
$$
p\in \left( \frac{x}{jN+1},\frac{x}{\left( j-1 \right) N+1} \right] \cap \left( x^{\frac{1}{3}},x^{\frac{1}{2}} \right]
$$
而这个区间最大值也只有$x^{1/2}$，因此只需要用小于等于 $x^{1/4}$ 的质数沿用线性筛的方法去筛出其中质数，然后计算 $\pi\left(\frac{x}{p}\right)$ 即可（不难验证，每个这样的区间长度仍然是小于等于 $x^{1/3}$ 的）。
综上，不难看出，在处理 $P_{2}(x,a)$ 的过程中，对于$x^{1/3}$ 个区间，处理每个区间的复杂度是$O(n^{1/3})$，同时除了第一个区间存下的质数表，剩下的每个区间真正有用的只有末尾的 $\pi(jN)$ （符合条件的 $\pi(\frac{x}{p_b})$ 只需要做一个累加的操作，不需要存储）、$\pi(x^{1/2})$、$\pi(x^{1/3})$ 的值，因此空间复杂度为$O(1)$。因此，完成处理完 $P_{2}(x,a)$ 所需的时间复杂度为$O(n^{2/3})$，空间复杂度为$O(n^{1/3})$。
那么接下来我们要处理的就是 $\phi(x,a)$ 了。回想一下 $\phi(x,a)$ 的定义，他的定义是“不大于$x$的数中，分解后不含前$a$个质数的数的个数”，我们采取一种分而治之的策略去处理它（其实有点像dp）。不难发现，它的定义等价于“不大于$x$的数中，分解后不含前$a-1$个质数的数的个数”减去“不大于$x$的数中，不含有前$a-1$个数但却是$a$的倍数的数的个数”而减去的一部分实际上等价于“不大于 $\frac{x}{p_a}$ 的数中，分解后不含前$a-1$个质数的数的个数”。也就是说，$\phi(x,a)$ 等于 $\phi(x,a-1)$ 减去 $\phi\left(\frac{x}{p_a},a-1\right)$ 。那么利用这个关系递归下去，不难得出这样一张关系图：
其实稍作推理就会发现，如果我们把每一项记做 $\phi\left(\frac{x}{n},b\right)$，那他的系数不就是莫比乌斯函数 $\mu(n)$ 吗！而对于莫比乌斯函数，我们是可以用线性筛法在线性时间复杂度内筛出来的。
但是如果我们真的这样一层层递归下来求解，那么显然需要计算/记录的东西和$a$是呈指数关系的。这无论在空间上还是时间上都是无法接受的。
那么如果我们能通过给出一些限制条件，当这棵树的节点达到这个限制条件时，我们就不继续伸展下去、而是开始计算，那也许就可以大大降低复杂度。原作者所给出的限制条件有两种：
(考试周结束再更了。。。要挂了。。。)
