To check if a number is prime or not.

Question

To check whether or not a naturel number, say $n$, is a prime number, we only need to check it with prime numbers less than or equal to its half($\frac{n}{2}$) rather than all odd numbers till it's half ($\frac{n}{2}$).Why so??

Answer 1

Take any $n\in \mathbb{N}-\{0,1\}$. If $n$ is not prime, then there must be a prime number $p$ such that $p\leq\sqrt{n}$ and $p.k=n$ for some $k\in \mathbb{N}$. (If not, in other words, all primes which divide $n$ bigger then $\sqrt{n}$, take two of them $p_1, p_2$ and we get $n\geq p_1.p_2>\sqrt{n}.\sqrt{n}=n$, then we have a contradicition)

Answer 2

Oh..... I see you weren't asking why you don't check the number $> \sqrt n$.

You were asking why you only check prime numbers and why not composite numbers?

Well, by the time you get ready to check a composite number you would have already checked all the prime numbers less than it. And those prime numbers failed. But those numbers include the prime factors of the composite number. If the prime factors failed then the number is going to fail and there is no point in checking it.

For example if $2$ fails then $4,6,8,10$ etc are all going to fail. If $3$ failed then $6,9,12,15,$ etc are all going to fail. If you get to $15$ and $3$ has already failed then there is no point in checking $15$ because $3$ already failed so you know $15$ will fail as well.

=====

Factors come in pairs.

If $n$ is composite then $n = km$ for integers $k$ and $m$ and neither $k$ nor $m$ equal $1$.

If one of them, say $k$, is less than or equal to $\sqrt n$ then the other, $m$, will have to be bigger than $\sqrt n$, and vice versa.

(Just think of it: if they worth both smaller than the square root of $n$ or both bigger than the square root of $n$ then the product will be less than or more than $n$.)

So if you checked all the values from $2...\sqrt n$ and none-of them were factors, then there won't be any values from $\sqrt n$ to $n-1$ that will pair up with them.

====old answer ====

If $k$ is a factor of $n$ then there is an $m$ so that $km =n$.

If $k > \sqrt {n}$ and $m > \sqrt{n}$ then $n = km > \sqrt n \sqrt n = n$ and that's a contradiction.

So one of $k$ or $m$ is less than or equal to $\sqrt n$.

So if there are any factors there are factors less than or equal to $ \sqrt n$.

So if you check all the integers up to $\sqrt n$ and you don't find a factor then .... there isn't any.

....

or to put it another way.

Suppose $2, ..... \lfloor \sqrt n \rfloor$ are not factors of $n$.

But suppose $k > \sqrt n $ is. Then $m = \frac {n}k$ is also a factor of $n$. But $k > \sqrt n$ so $m < \frac {n}{\sqrt n} = \sqrt {n}$.

But $2, ..... \lfloor \sqrt n \rfloor$ are not factors. So the only option for $m$ is if $m =1$.

But if $m = \frac nk =1$ then $k = n$.

So $1$ and $n$ are the only factors of $n$ and $n$ is prime.