elementary number theory - Why does $lfloorfrac{n}{x}rfloor$ have at most $2sqrt{n}$ values when $x=1,2,dots n$?

The question is very short and clear:

Why does $\lfloor\frac{n}{x}\rfloor$ (floor of $\frac nx$) have at most $2\sqrt{n}$ values when $x = 1, 2,\dots, n$?

I saw this statement at tutorial of 449A at codeforces, I really want to know how we get that, and since the amount of values should be integer, why $2\sqrt{n}$?

And I don't know the specific category of this problem so I just tag it as elementary number theory.

Answer

Over the range $1 \le x \le \sqrt{n}$, $x$ can take on only $\sqrt{n}$ distinct integer values. Thus, $\left\lfloor\dfrac{n}{x}\right\rfloor$ can only take on $\sqrt{n}$ distinct values, one for each distinct value of $x$.

Over the range $\sqrt{n} \le x \le n$, we have that $1 \le \dfrac{n}{x} \le \sqrt{n}$. Thus, $\left\lfloor\dfrac{n}{x}\right\rfloor$ can only take on $\sqrt{n}$ distinct values, one for each integer between $1$ and $\sqrt{n}$.

This adds up to $2\sqrt{n}$ values over the entire range $1 \le x \le n$.

Note that this is an upper bound and not an exact number. For instance, if $n = 6$, then we have at most $2\sqrt{6} \approx 4.89$ values. Indeed, $\lfloor\frac{6}{1}\rfloor = 6$, $\lfloor\frac{6}{2}\rfloor = 3$, $\lfloor\frac{6}{3}\rfloor = 2$, $\lfloor\frac{6}{4}\rfloor = \lfloor\frac{6}{5}\rfloor = \lfloor\frac{6}{6}\rfloor = 1$, so we have $4$ distinct values.