线筛妙用

一些奇怪的东西…

求： $$\sum _{i=1}^n{i}^k$$

经典的自然数幂和，$n<5e6$，用最简的方法。 在线筛的时候暴力把每个质数的k次方暴力算，非质数的线筛时乘到一起即可 因为质数很少，所以跑的飞快。