§ Cost of looping over all multiples of $i$ for $i$ in $1$ to $N$

• 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