A Universe of Sorts

Intuitively, when I think of "looping over $i$ and all its multiples", I seem to have a gut feeling that its cost is $N$ . Of course, it is not. It is $N/i$ .
Thus, the correct total cost becomes $\sum_{i=1}^N N/i$ (versus the false cost of $\sum_{i=1}^N N = N^2$ .
The correct total cost is a harmonic series $N\cdot \sum_{i=1}^N1/i \simeq N \log N$ .
This is useful for number theory problems like 1627D

§ Cost of Looping over All Multiples of iii for iii in 111 To NNN