The Meissel, Lehmer, Lagarias, Miller, Odlyzko method (1996)（一）
ケロシ
·
·
题解
相信大家已经学会了 Computing \pi(x): The Meissel-Lehmer method(1985)，（存疑
今天我们来学一种更厉害的算法：Computing \pi(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method (1996)
由于太过复杂，我们今天先讲一个超级弱化版。
一些记号
$p$ 表示某个素数，$p_i$ 表示第 $i$ 个素数。
## 计算 $\pi(x)
我们定义两个函数。
$$
\phi(x,a)= | \{ n \le x : p \mid n \Rightarrow p > p_a \} |
$$
$P_k(x,a)$ 表示小于等于 $x$ 的数中，有多少个是由 $k$ 个大于 $p_a$ 的质数相乘得来，即：
$$
P_k(x,a)= \left | \left \{ n \le x : n = \prod_{j=1}^{k}p_{m_j},m_j > a \right \} \right |
$$
不难发现等式：
$$
\phi(x,a)=P_0(x,a)+P_1(x,a)+P_2(x,a)+\cdots
$$
不难发现若 $p_a \ge x^\frac{1}{3}$，则对于 $k \ge 3$ 的 $P_k(x,a)$ 都是 $0$。
所以取 $y=\left \lfloor x^\frac{1}{3} \right \rfloor $，$a=\pi(y)$，那么有：
$$
\phi(x,a)=P_0(x,a)+P_1(x,a)+P_2(x,a)
$$
$$
\phi(x,a)=1 + \pi(x)-a+P_2(x,a)
$$
$$
\pi(x)=\phi(x,a) - P_2(x,a) + a - 1
$$
## 计算 $P_2(x,a)
枚举小的质数，那么：
P_2(x,a)=
\sum_{y < p \le x^\frac{1}{2}}
\pi \left ( \frac{n}{p} \right )
- \pi(p) + 1
计算 \phi(x,a)
考虑在 \phi(x,a-1) 的基础上筛掉最小质因数为 p_a 的数：
\phi(x,a) = \phi(x, a - 1) - \phi \left (\frac{x}{p_a},a-1 \right )
终止条件：\phi(x,0)=x。
剪枝一：
若 p_a^2 \ge x，则返回 \max(\pi(x)-a,0)+1。
剪枝二：
把 x,a 小的 \phi(x,a) 记忆化掉，此时就可以通过洛谷的模板题。