这儿只是一个简单说明/概括/总结。
原理见这：
https://www.cnblogs.com/cjyyb/p/9185093.html
https://www.cnblogs.com/zhoushuyu/p/9187319.html
首先计算$$g(n,j)=sum_if(i),quad i是质数 或 i的最小质因子严格大于P_jg(n,j)=egin{cases}g(n,j-1)&P_j^2gt n g(n,j-1)-f(P_j)left[g(frac{n}{P_j},j-1)-sum_{i=1}^{j-1}f(P_i) ight]&P_j^2le nend{cases}$$
类似埃氏筛法，(P(n,j))就是筛(j)次后剩下的数的(f)和，再加上所有质数(p)的(f(p))之和。
(P_j^2>n)时，这一次筛不会筛掉任何数，所以就是(g(n,j-1))。
(P_j^2leq n)时，考虑第(j)次筛掉了哪些数，也就是最小质因子是(P_j)的那些数。因为是积性函数，所以我们直接提出一个(P_j)（来保证它含(P_j)）。
要被筛掉的数在除掉一个(P_j)后的最小质因子一定仍大于等于(P_j)（否则在之前就被筛掉了），这符合(g(frac{n}{P_j},j-1))的定义。所以减掉一个(f(P_j)g(frac{n}{P_j},j-1))。但是(g(frac{n}{P_j},j-1))还包含所有质数的(f(p))之和，所以再加上(sum_{i=1}^{j-1}f(P_i))。
那初值呢？先把所有合数的(f)的计算方式看做和质数一样，以便对所有数的(f)值快速求个和，用它作为(g(n,0))（注意这里不考虑(1)）。这样虽然合数的(f)值是假的，但是(g(n,|P|))还是能正确的表示所有质数(p)的(f(p))之和。
现在考虑算上合数的(f)值求和。令$$S(n,j)=sum_if(i),quad i是质数 或 i的最小质因子大于等于P_j$$
我们把(S(n,j))分两部分计算，一是所有质数的贡献，二是所有合数的贡献。对于(f(1))最后单独算下。
那么所有质数的贡献可以用(g)表示，也就是(g(n,j)-sum_{i=1}^{j-1}f(P_i))（因为最小质因子要大于等于(P_j)，所以把那些减掉）。
对于合数，枚举这个合数的最小质因子及其次数，用(f)是积性函数的性质直接算：$$S(n,j)=g(n,j)-sum_{i=1}^{j-1}f(P_i)+sum_{k=j}^{P_k^2leq n}sum_{e=1}^{P_k^{e+1}leq n}left[f(P_k^e) imes S(frac{n}{P_k^e},k+1)+f(P_k^{e+1}) ight]$$
(f(P_k^{e+1}))是(S)没有考虑的那部分（就是(P_k^{e+1})，质数的若干次幂这样的合数，而(S(..,k+1))就把这些数忽略掉了）。
答案就是(S(n,1)+f(1))。
流程：
-
把所有合数看做质数，求一遍和，得到初值(g(n,0))。同时预处理一个(f(P_i))的前缀和。
-
用$$g(n,j)=egin{cases}g(n,j-1)&P_j^2gt n g(n,j-1)-f(P_j)left[g(frac{n}{P_j},j-1)-sum_{i=1}^{j-1}f(P_i) ight]&P_j^2le nend{cases}$$
计算(g(x,|P|))（把第二维滚动掉）。 -
用$$S(n,j)=g(n,j)-sum_{i=1}^{j-1}f(P_i)+sum_{k=j}^{P_k^2leq n}sum_{e=1}^{P_k^{e+1}leq n}left[f(P_k^e) imes S(frac{n}{P_k^e},k+1)+f(P_k^{e+1}) ight]$$
计算(S(n,1)+f(1))。
计算(S,g)的复杂度都是(O(frac{n^{frac34}}{log n}))。
对于其它积性函数，同(g)一样计算。
实现上，筛(sqrt(n))内的质数这一步往往可以省略，见这里。
例题：
LOJ6235 区间素数个数
BZOJ3944 Sum
LOJ6053 简单的函数
以后要做的题：
https://cmxrynp.github.io/2018/12/03/Min-25筛学习笔记/
https://blog.csdn.net/koishi_514/article/details/79485534
https://blog.csdn.net/HOWARLI/article/details/80339931