那个什么筛？
by impuk @ 2020-05-30 21:43:50
Min25 筛，LOJ 的 区间素数
by 1saunoya @ 2020-05-30 21:44:10
感觉分块打表也行……
by impuk @ 2020-05-30 21:47:52
<https://www.ams.org/journals/mcom/1996-65-213/S0025-5718-96-00674-6/S0025-5718-96-00674-6.pdf>
这玩意时间 $O\left(\dfrac{n^{2/3}}{\log^2n}\right)$，空间 $O(n^{1/3}\log^3n\log\log n)$，跑起 $10^{12}$ 毫无压力
by Hirasawa_Yui @ 2020-05-30 21:48:23
啊，就我一个蓝名
by Hirasawa_Yui @ 2020-05-30 21:48:49
如果不考虑常数的话，还有一篇 paper：<http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf>
它能在 $O(n^{1/2+\epsilon})$ 的时间以及 $O(n^{1/4+\epsilon})$ 的空间内解决你的问题，但是复杂度上天，在 $\le 10^{17}$ 的时候都没法跟前一个比
by Hirasawa_Yui @ 2020-05-30 21:55:57
如果只是要过题的话，min_25 筛够用了，<https://oi-wiki.org/math/min-25/>
by Hirasawa_Yui @ 2020-05-30 21:58:33
@[w33z8kqrqk8zzzx33](/user/220037)
by Hirasawa_Yui @ 2020-05-30 21:58:44
%%%%楼上
by xhQYm @ 2020-05-30 22:10:23