Why is it useful to calculate the square root when performing Primality test?

Question

From Wikipedia (emphasis mine):

The most basic method of checking the primality of a given integer n is called trial division. This routine consists of dividing n by each integer m that is greater than 1 and less than or equal to the square root of n. If the result of any of these divisions is an integer, then n is not a prime, otherwise it is a prime.

Why do we assume that if n is not a product of any number between 2 and sqrt(n) it is also not a product of any number higher than sqrt(n)?

Answer 1

If $n$ is not prime then $n=ab$ where both factors are less than $n$. They can't both be greater than $\sqrt{n}$, so in your search if you get to $\sqrt{n}$ without finding a factor you'll never find one so can stop searching.

If you're interested in finding primes you might want to check out the Sieve of Eratosthenes.

Answer 2

If we have a factor $f>\sqrt{N}$ , then $$f':=\frac{N}{f}<\frac{N}{\sqrt{N}}= \sqrt{N}$$ is a factor as well , so we only need to check until the square root.