rt,我研究了这个的最后一个式子。抛开多次杜教筛复杂度不谈，对于其整除分块的复杂度有疑问。
具体的，求 $\sum\limits_{d=1}^n \sum\limits_{i=1}^{\lfloor\frac n d\rfloor} \sum\limits_{j=1}^{\lfloor\frac n{di}\rfloor}$ 的复杂度。
第一次整除分块显然是 $\sqrt N$ 的，但是第二次依赖于第一次剩下的值，整除分块剩下的值本身十分玄学，并且不具有连续性，所以不会进一步分析。

有一个问题，假设 $\lfloor \frac n d \rfloor$ 取遍从 $1$ 到 $\sqrt n$，则复杂度是 $\sum\limits_{i=1}^{\sqrt n}\sqrt i$ 的，近似看作 $\int\limits_{i=1}^{\sqrt n}\sqrt i$ 的，解出来是 $O(n^{\sqrt \frac 3 2})$。
考虑实际情况，$\lfloor \frac n d \rfloor$ 对应的序列总存在一个顺序满足每一项都不小于假定的 $1\to\sqrt n$序列。所以分析出来是 $O(\text{实际}) \gt O(n^{\sqrt \frac 3 2}) \gt O(n)$ 的。
感觉很不对，因为 $n$ 是 $10^9$ 级别的。