用于求 ,复杂度“据说”是 ,会比杜教筛略快
需满足 是积性函数,且 是关于 的低次多项式(如果次数过高,需要用拉格朗日插值求系数) 中定义了两个函数:
是质数位上的前缀和, 就是答案。
又当 即 时 才不为 , 故
,因为
当 时 ,将上式求和,得:
将 的过程改为递推,可以求出所有给