这是一篇筛 $\pi(n)$ 的文章。
主要讲解 $\text{Meissel}$ 筛 , 其它的两种筛都不赘述。
这篇文章还能让你在回答质数问题的时候不至于脱口而出“洲阁筛”“$\text{Min_25}$”。

参考 :
$\text{知乎原帖}$ : 启蒙读物。

这篇文章可以得出 , 用容斥原理做出来的简单筛子可以拓展到积性函数筛。
混了一下就知道 , 如果要更快 , 右转积分强行压界。
直接应用原文 :
$\text{Hedgehog}$ 筛法 : $\text S(v,p)=\text S(v,p-1)-p(\text S(\left\lfloor\frac{n}{p} \right\rfloor,p-1)-\text S(p-1,p-1))$。 (详见 $\text{菜鱼ftfish}$ 的回答)
$\text{Min_25}$ 筛素数函数值 : $\text G_k(n)=\text G_{k-1}(n)-[p_k^2 \leq n]g(p_k)(\text G_{k-1}(\left\lfloor\frac{n}{p_k} \right\rfloor)-\text G_{k-1}(p_k-1))$ 。 (详见 $\text{OI-Wiki}$)
$\text{Lehmer}$ 筛法 : $\phi(x,a)=\phi(x,a-1)-\phi(\left\lfloor\frac{x}{p_a}\right\rfloor,a-1)$ 。 (详见 $\text{穆罕默德·李}$ 的回答)
洲阁筛筛素数函数值 ： $g_{i,j}=g_{i-1,j}-f(p_i)g_{i-1,\left\lfloor\frac{j}{p_i}\right\rfloor}$。 (翻我的博客就行)

难道这是巧合 ?
我只是想建议大家在回答问题筛质数的时候不要回答 $\text{Min_25}$ 或者洲阁筛了。
但这不是本文重点。
本文主要讲 $\text{Meissel}$ 筛 , 一种 $O(n \ln^{-3} n)$ 时间 , $O(n^{\frac 1 2} \ln^{-1} n)$ 空间的筛素数的方法。
这种筛法也就只有你乎和朱姥爷的论文有了 , 当然 $\text{DR}$ 是不可能学会的。

考虑 $\text{Lehmer}$ 筛法 ,