(Oleft(sqrt{n} ight)) 种取值。

(n) 除并下取整取值相同的一段区间的右端点。

(leftlfloorfrac{n}{ab} ight floor=leftlfloorfrac{leftlfloorfrac{n}{a} ight floor}{b} ight floor=leftlfloorfrac{leftlfloorfrac{n}{b} ight floor}{a} ight floor)

应用：

(S(n) = 1 - sum_{i=2}^n S(lfloor frac{n}{i} floor))。

(S(n) = frac{n(n+1)}{2} - sum_{i=2}^n S(lfloor frac{n}{i} floor))。

还有求各种积性函数的前缀和....

(O(frac{n^{3/4}}{logn})) ，一般情况下，洲阁筛的常数和复杂度都更加优秀。但现在好像有种比洲阁筛更优秀一点的筛法。(https://post.icpc-camp.org/d/782-spoj-divcnt3/2)(可能要科学上网...)

(O(n^{2/3}))左右可以使复杂度更优秀一些，一般会使用记忆化搜索和哈希表，map也可以代替哈希表。