Powerful Number 筛

[Enter-tainer]

https://oi-wiki.org/math/number-theory/powerful-number/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[0x3b800001]

这第一部分复杂度不是 $O(\frac{\sqrt n}{\log n})$ 吗？根号分治可以直接估出来这个界吧。

[0x3b800001]

实际上对于任何多项式函数 $f(x)$ 都有 $\sum\limits_{p\le n, p \text{ is prime}}f(\log_pn)=O(\frac{\sqrt n}{\log n})$。同样是根号分治易证的。

[fqfengqi]

Min_25筛例题推导的第三行 当k-i为0的时候没有p因子