杜教筛用来求数论函数\(f\)前缀和。复杂度为\(O(n^{\frac{2}{3}})\)
前提如果我们要求\(S(n)=\sum\limits_{i=1}^nf(i)\)，那么需要找到一个数论函数\(g\)，满足\(g\)的前缀和可以非常快速的求出来，并且\(g*f\)的前缀和可以非常快速的求出来。
推导既然\(g*f\)的前缀和可以非常快速的求出来，我们就求\(g*f\)的前缀和。
即\(\sum\limits_{i=1}^n\sum\limits_{d|i}g(\frac{i}{d})f(d)\)。
然后我们想得到的是\(\sum\limits_{i=1}^nf(i)\)。所以我们让上面的式子减去一个\(\sum\limits_{i=1}^n\sum\limits_{d|i,d\neq i}g(\frac{i}{d})f(d)\)。
对于后面这个式子,我们用\(\frac{n}{d}\)来代替\(d\)，就变成了
\[\sum\limits_{i=1}^n\sum\limits_{d\neq 1,d|i}g(d)f(\frac{i}{d}) \]