我们先枚举一个最大质因子，然后设 \(dp[n][k]\) 为 \(n\) 以内使用了 \(pri[k]\) 以内的质数的数的最大质因子之和，答案就是：

当 \(pri[k]\) 大于 \(\sqrt{n}\) 时，后面相当于变成 \(\sqrt{n}\) 以内所有数的最大质因子之和，可以线性筛，质数个数也可以使用叶筛解决。

考虑这个 \(dp\) 怎么办。

根据上面的东西，我们设一个 \(g[n][k]\) 为 \(n\) 以内使用了 \(pri[k]\) 以内的质数的数的个数。有：

只要一边筛 \(g\) 一边丢到 \(dp\) 数组里边就好了。

但是注意到丢进去的复杂度是 \(O(\frac{n}{\ln^2n})\) 的，考虑优化。。。

这个 \(g\) 是十分经典的叶筛。\(g\) 的定义为仅用过 \([1,pri[k]]\) 的质数，叶筛的 \(f\) 定义为 \([1,pri[k]]\) 的的质数都没被使用过，即最小质因子为 \(pri[k]\)。

转移可以参考这个过程。得到有：

注意到其实增加的这一部分（\(g[\frac{n}{pri[k]}][k]\)）其实就是不大于 \(n\) 的最大质因子为 \(pri[k]\) 的数的数量。

直接顶上去代替 \(dp\) 不就好了。

转移的话可以使用叶筛的那种转移，滚动数组就好了（）

实际上，对于一个 \(g[n][k]\)，有用的状态数量只有 \(O(\frac{n^{\frac{3}{4}}}{\ln n})\) 个，可以直接进行区间加什么的。

复杂度 \(O(\frac{n^{\frac{3}{4}}}{\ln n})\)。