Prove that $d(n)\leq 2\sqrt{n}$ In Waclaw Sierpinski's book Elementary Theory of Numbers on page 168 there is the following exercise:
"Exercises. 1. Prove that for natural numbers $n$ we have $d(n) \leq 2\sqrt{n}$," where $d(n)$ is the number of divisors of n.
As a hint right below is given: "The proof follows from the fact that of two complementary divisors of a natural number $n$ one is always not greater than $\sqrt{n}$.
I understand the hint but I don't know how it can be used to prove $d(n)\leq 2\sqrt{n}$.
Complementary divisors are pairs of divisors that when multiplied gives the number that is to be divided. For example the number $120$ has the complementary divisors:
\begin{align*}
& 1, 120 \\
& 2, 60 \\
& 3, 40 \\
& 4, 30 \\
& 5, 24 \\
& 6, 20 \\
& 8, 15 \\
& 10, 12 \\
\end{align*}
How do you prove that $d(n) \leq 2\sqrt{n}$?
 A: The function which sends a divisor $d$ of $n$ to the smallest of $d$ and $n/d$ is at most $2$-to-$1$ hence the size of the source set is at most twice the size of the target set. The source set is the set of divisors of $n$ and has size $d(n)$. The target set is made of (some) positive integers not greater than $\sqrt{n}$ hence it has size at most $\sqrt{n}$. QED.
A: Consider the ordered pairs of complementary divisors of $n$,
$(d_1,\frac nd_1),(d_2,\frac nd_2),\dots,(d_r,\frac nd_r),(\sqrt n,\sqrt n),(\frac nd_1,d_1),(\frac nd_2,d_2),\dots,(\frac nd_r,d_r)$
where $d_i\le\sqrt n\quad\forall i=1,2,\dots,r$
If $n$ is not a perfect square we exclude $(\sqrt n,\sqrt n)$. Let $S=\{(d_1,\frac nd_1),(d_2,\frac nd_2),\dots,(d_s,\frac nd_s)\}$ be the set of all the ordered pair where the first elements are $d_i's$; $d_s=d_r$ if $n$ is not a perfect square and $d_s=\sqrt n$ if $n$ is a perfect square. Let $m$ denote the number of elements of $S$. It is clear that $$d(n)\le2m\dots(1)\Bigl(d(n)\lt2m,\text{if $n$ is a perfect square and $d(n)=2m$ if $n$ is not a perfect square$\Bigl)$}$$ The number of elements of $S$ is equal to the number of $d_i's$. Suppose $n$ is divisible by all integers $\le\sqrt n\;$, then $d_1=1,d_2=2,d_3=3,\dots d_s=\sqrt n,$ then the number of $d_i's$ is $\sqrt n\;$ and therefore the number of $d_i's$ is at most $\sqrt n\,$. Thus, for every integer $n\ge 1$, the number of $d_i's\le\sqrt n\,$. Then, $$m\le\sqrt n\,\dots(2)$$ Now from equation $(1)$ and $(2)$, we get $$d(n)\le2\sqrt n$$
A: Suppose first that $n$ is not a square. Then to each divisor less than $\sqrt{n}$ there is one and only one "complementary" divisor which is greater than $\sqrt{n}$. So the number of divisors of $n$ is equal to twice the number of divisors of $n$ that are smaller than $\sqrt{n}$. 
How many divisors can $n$ have that are smaller than $\sqrt{n}$? Can you give a very trivial upper bound to that quantity?
The argument is essentially the same if $n$ is a perfect square, except that in that case you have one special divisor, namely, $\sqrt{n}$, which is not paired up with anyone. Yet the bounding argument should still be (essentially) the same.
