看不懂别人博客里写的代码，所以只好自己实现常数超大的版本了，，，
记号：
\[\begin{aligned} \mathbf P&:\text{质数集}\\ p_k&:\text{第 k 个质数}\\ \text{lpf}(n)&:\text{n 的最小质因子}\\ x/y&:\left\lfloor\dfrac xy\right\rfloor \end{aligned} \]前置知识：
\(n\) 的块筛，指 \(n/i\) 的 \(O(\sqrt n)\) 种取值。
用整除分块可以轻松求出 \(n\) 的块筛，并给它们编号：
L = sqrt(n);
for (int l = 1, r; l <= n; l = r + 1)
{
r = n / (n / l), v[++_] = n / l;
if (v[_] <= L)
o1[v[_]] = _;
else
o2[n / v[_]] = _;
}
// 此时 v 中从大到小存储 n 的块筛
int O(int x) { return x <= L ? o1[x] : o2[n / x]; } // 返回 x 是从大到小第几个块筛
给定数论函数 \(f\)。\(\forall p\in\mathbf P\)，\(f(p)\) 是关于 \(p\) 的少项式，\(f(p^k)\) 可以快速求值。给定 \(n\)，求 \(\sum\limits_{i=1}^nf(i)\)。
Part I 还没写代码，别急。
Part II 求前缀质数处的和
即求 \(\sum\limits_{p\in\mathbf P,p\le n}f(p)\)。
Min_25 筛为啥叫 ex埃筛 呢？
上面提到，\(f(p)\) 是关于 \(p\) 的少项式（假设有 \(o\) 项），即 \(f(p)=\sum\limits_{i=1}^oa_ip^{s_i}\)，则 \(\sum\limits_{p\in\mathbf P,p\le n}f(p)=\sum\limits_{i=1}^oa_i\sum\limits_{p\in\mathbf P,p\le n}p^{s_i}\)。
于是对于少项式的每一项，我们只需要求 \(\sum\limits_{p\in\mathbf P,p\le n}p^{s_i}\)，设 \(g(n)=n^{s_i}\)。
模拟埃筛的过程，设 \(G_{k,n}\) 表示 \(\sum\limits_{i=1}^n[\text{lpf}(i)>p_k\vee i\in\mathbf P]g(i)\)，即第 \(k\) 轮埃筛（筛去 \(p_k\) 的倍数）后剩下的位置的 \(g\) 值之和。
埃筛只用筛 \(\sqrt n\) 轮，所以设 \(p_c\) 为 \(\sqrt n\) 以内最大的质数，则答案为 \(G_{c,n}\)。
Min_25
考虑算 \(G_{k,n}\)。
筛完 \(k-1\) 轮，剩下的位置的 \(g\) 值之和为 \(G_{k-1,n}\)。
第 \(k\) 轮需要筛掉 \(p_k\) 的倍数，也就是说 \(G_{k,n}=G_{k-1,n}-\sum\limits_{i=1}^n[\text{lpf}(i)=p_k]g(i)\)。
标签：25,26,mathbf,limits,Min,text,sum From： https://www.cnblogs.com/5k-sync-closer/p/18408377