Understanding the trial division primality test I'm reading an algorithms book and I came across a code example for a primality test. The problem is that I couldn't understand the condition for the for-loop:
public static boolean isPrime( int N ) {
        if (N < 2) return false;
        for ( int i = 2; i * i < N; i++ ) {
            if ( N % i == 0 )
                return false;
        }

        return true;
}

If we multiply i by itself we would miss a lot of numbers to check. So if we want to check if n=10 is prime or not, then we would quickly end the loop by i=3. I know that the idea is finish the loop as early as possible, but how do we guarantee that by using that condition we are actually checking all possible divisors and the rest that we omitted are never going to be divisors?
This condition seems quite common and popular but I really wasn't able to understand it or find an interpretation. I understood the condition i < n/2 but not that one. I hope I'm not stupid!
 A: Note that if $n$ is composite, then $n$ has a non-trivial factor $i$ such that $i \le \sqrt{n}$.  Otherwise, any nontrivial factorization $n = ab$ would force $a, b > \sqrt{n}$, so that $n = ab >  \sqrt{n}\times \sqrt{n} = n$, a contradiction.
A: The trial division test, abstractly formulated, is this: for each number $i$ in some suitable set, check whether $i$ divides $n$.  If one such number is found, output "$n$ is composite", else output "$n$ is prime".  (Perhaps you need to special-case $n=1$; I'll leave that to the reader).
Clearly no suitable set can contain $1$ or $n$, or we would report all numbers to be composite.  No number is divisible by zero, and a number is divisible by $-x$ iff it is divisible by $x$, so we don't need to check numbers less than $1$.  Also, if $m > n$ then $m$ does not divide $n$, so the set $\{2..n-1\}$ is definitely good enough: if we check all those numbers (and only those), then we are guaranteed to output the correct answer.  It can be large, though, so we would like to thin it out if we can.

How do we guarantee that by using that condition we are actually
  checking all possible divisors and the rest that we omitted are never
  going to be divisors?

If $n / i$ is an integer, let's call it $k$, then definitely $n / k = n / (n/i) = i$ is also an integer.  In other words, if $n = ik$ with $i < k$, then when you check for $i$ you indirectly also check for $k$: if $n$ can be factored into two non-trivial factors, finding the smaller of the two is finding at least one such factor (from which you can conclude that it's composite), and if $n$ can't be factored so, no such smaller-of-the-two factor will exist.
So, if instead of $\{2..n-1\}$ you only look at from 2 up to the largest of any possible smallest-factor-in-a-pair, you have still looked at enough possible candidates to be certain in your conclusion.  Other people have already explained why $\sqrt{n}$ is the limit.
There is some subtlety in why $\lfloor\sqrt{n}\rfloor$, which is really what is being checked, is also good enough: either $\lfloor\sqrt{n}\rfloor = \lceil(\sqrt{n})\rceil = \sqrt{n}$ or $\lceil(\sqrt{n})\rceil^2 > n$, so either you have checked $\lceil(\sqrt{n})\rceil$ also, or you don't need to.
A: If $n$ is not prime, then at least one of the factors of $n$ is at most as large as $\sqrt n$. To see why, let's suppose not. Since $n$ is not prime, $n = ab$ for some $a,b \neq 1$. If both $a$ and $b$ are larger than $\sqrt n$, then $a\cdot b > \sqrt n \cdot \sqrt n = n$. This clearly cannot be!
So you only need to check for factors up to $\sqrt n$.
A: It may be worth mentioning that if $n$ is composite it has a prime factor less than or equal to $\sqrt{n}$.  So in this 'trial division' algorithm, you only have to test $n$ for divisibility by primes up to $\sqrt{n}$.
