Floor-division grouping
= Floor-division grouping
For a positive <integer> $n$, indices with the same quotient $q=\lfloor n/i\rfloor$ form intervals. If an interval begins at $l$, it ends at $r=\lfloor n/q\rfloor$. There are $O(\sqrt n)$ distinct quotients: either $i\le\sqrt n$, or the quotient is below $\sqrt n$. This permits summing constant-quotient blocks instead of visiting every index.