终于知道发明者的正确的名字了,是Min_25,这个筛法速度为亚线性的\(O(\frac{n^{\frac{3}{4}}}{\log x})\),用于求解具有下面性质的积性函数的前缀和:

  1. 在 \(p\) 处是简单的低次多项式
  2. 在 \(p^c\) 处可以快速求值

貌似积性函数是指取一个积性函数 \(f(x)\) ,其在质数的位置上取值与所求函数相同。所以可以用来求n以内的质数的个数(取常函数 \(f(x)=1\) )以及质数的和(取恒等函数 \(f(x)=x\) )。

参考资料:

loj#6235. 区间素数个数(min25筛) - 自为风月马前卒 - 博客园
关于min_25筛的一些理解 - GuessYCB - 博客园
2019徐州网络赛 H.function - heyuhhh - 博客园

05-11 15:39