if $n\in\mathbb{N}$ and $n \mod 2,..., n\mod \text{floor}\sqrt{n}\neq 0$ then $n$ is prime This was an algorithm to see whether a number is prime or not, but what is the justification. Why is it sufficient to check all number from $2$ to $\text{floor}\sqrt{n}$?

If you go through all numbers from $2$ to $m$ where $m$ is the biggest $m^2 \le n$ you will either find a number divisible by $n$ or you will not find it.
If you do, $n$ is not prime. If you don't, $n$ is prime, otherwise $n = k \cdot m$ for some $k$ and $m$ where $k^2 > n$ and $m^2 > n$, i.e. $k \cdot m > n$.
Therefore it's enough to check all numbers from $2$ to $\lfloor \sqrt{n} \rfloor$.
We say that the time complexity of the algorithm is $O(\sqrt{n})$.
For primes we can make it even better if we keep prior primes in memory. For that, we can go through only prime numbers, not through all numbers. 
In practice this does not make sense if we need to figure out whether some number prime or not. But it does if we need to find all primers up to some value.
If we use memory, then the time complexity will be $O\left(\frac{\sqrt{n}}{ln(\sqrt{n})}\right)$ for each n up to some number $N$, but we need $O\left(\frac{N}{ln(N)}\right)$ for memory. 
