To find whether $a$ is a prime number I have been using this rule to determine whether a number is a prime number, but not how to prove it. Why it has to be $\sqrt{a}$?

If $a$ is not divisible by all the prime numbers less than or equal to $\sqrt{a}$, then $a$ is a prime number.

 A: Just another point of view
Suppose that $a$ is divisible by a prime $p$. This means that:
$$a = p \cdot k \Rightarrow p = \frac{a}{k}.$$
Moreover, suppose that $p > \sqrt{a}$, then:
$$\frac{a}{k} > \sqrt{a} \Rightarrow k < \sqrt{a}.$$
This means that I can only use the primes $p \in [\sqrt{a}, a]$ to determine if $a$ is prime, instead of the set $[0, \sqrt{a}]$.
Which is the set that best suits for the algorithm? 
I guess the smallest, since you will have a smaller number of primes to be tested. The set $[\sqrt{a}, a]$ has length $a-\sqrt{a}$, while the set $[0, \sqrt{a}]$ has length $\sqrt{a}$. 
Notice that: 
$$\sqrt{a} < a-\sqrt{a} \Rightarrow 2\sqrt{a} < a \Rightarrow \sqrt{a} > 2 \Rightarrow a > 4.$$
In general, you want test a number $a$ bigger than $4$. For this reason, you just look to the set $[0, \sqrt{a}]$... it is just faster!

Example. 
Take $a = 77$ and notice that $\sqrt{a} \simeq 8.78$. If you use the set $[0, \sqrt{a}]$, the you will have to check if $a$ is divisible by $3,5,7$ (only three numbers). On the other hand, if you choose the set $[\sqrt{a}, a]$, you will have to check if $a$ is divisible by $11, 13, 17, 19, 23, 29, 31, 37, ...$. Hey, this is too much, no?! 
A: Let $ab=p$ where $a,b$ are possible factors of prime candidate $p$.
If you find a factor $b \geq \sqrt{p}$, then $a \leq \sqrt{p}$.
But if you checked all $a \leq \sqrt{p}$ and didn't find any factors ...
A: For every prime divisor of $n$ that is less than $n$ and greater than $\sqrt{n}$, there must be a prime number less than $\sqrt{n}$ that divides $n$. 
This follows from the fact that it is impossible for a number $n$ to have two prime divisors $p$ and $q$ that were both greater than $\sqrt{n}$, since then their product would be $$pq>(\sqrt{n})^2=n$$ 
Thus we need only check the primes in the range $1,...,\sqrt{n}$ to see if they divide $n$.   
A: This may be easiest to see if illustrated by example.
Consider the factors of $16$ as found by trial division.
That is, we will divide $16$ by $1$ then $2$ then... and each time the remainder is $0$ we will record both the divisor and the quotient as a factor pair:

$1$: Yes, this yields the factor pair $(1, 16)$.
$2$: Yes, this yields the factor pair $(2, 8)$.
$3$: No, $16/3$ is not a whole number, i.e., it has remainder $1$.
$4$: Yes, this yields the factor pair $(4,4)$.
$5$: No, $16/5$ is not a whole number, i.e., it has remainder $1$.
$6$: No, $16/6$ is not a whole number, i.e., it has remainder $4$.
$7$: No, $16/7$ is not a whole number, i.e., it has remainder $2$.
$8$: Yes, this yields the factor pair $(8,2)$.
$\ldots$

Note that we already had that last factor pair, though in the other order, as $(2,8)$.
Trying other examples and searching for factor pairs, you will always find that, at some point, they repeat. (If the number is prime, e.g., $11$, then the only factor pairs will be $(1, 11)$ and $(11, 1)$.)
The question now becomes, at what point do the numbers repeat? That is, when can we stop carrying out our trial division?
For the case of $16$ they repeat after $\sqrt{16} = 4$.
More generally, all the factors appear in this way once you check up to the square root.
For if the target number is $N$ and you've found all factors less than or equal to $\sqrt{N}$, could there be new factors? If so, you'd need to find a factor pair with two new factors, i.e., each of which is greater than $\sqrt{N}$.
But then their product would be greater than $\sqrt{N}\sqrt{N} = N$; so, they cannot form a factor pair: Their product is bigger than the target number!
A: Assume $a$ is not a prime number. Then it can be written as $a = bc$ with $b, c \ge 2$. Then the smaller of $b, c$ is less than or equal to $\sqrt a$, for otherwise the product would be greater than $\sqrt a \, \sqrt a = a$. This smaller factor is then either a prime itself or has a prime factor that is even smaller.
A: Divisors come in pairs. If $n$ divides $a$, so does $a/n$, as $\sqrt{a}\sqrt{a}=a$, one of the factors in a pair must be smaller than or equal to $\sqrt{a}$.
