To check if a number is prime or not.

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??

• Actually till $\sqrt{n}$ is enought. Jan 27 '19 at 1:18
• How so??If I could get the result mathematically Jan 27 '19 at 1:20
• @PratyushKumar: if a number $n$ is composite, say $n=ab$, then at least one between $a$ and $b$ is $\leq\sqrt{n}$. If you rule out the existence of prime divisors $\leq\sqrt{n}$ it follows that $n$ is a prime. Jan 27 '19 at 1:23
• This link should help... Jan 27 '19 at 1:23
• Suppose $n$ is not prime and the smallest prime that divides $n$ is $>\sqrt{n}$ Jan 27 '19 at 1:23

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)

• Ok...but why not all odd numbers till it's root rather than only prime numbers till it's root Jan 27 '19 at 1:41
• Suppose you checkt it out for an odd number smaller then $\sqrt{n}$, and you see that it divides $n$. If the odd number is not prime, there must be a prime number which divides the odd number. So this prime number is smaller than the odd number, and so, smaller than $\sqrt{n}$. So ıf you just use primes , they will be enought. Jan 27 '19 at 1:52
• Oo... thanks... Jan 27 '19 at 1:56
• Should be $p\le \sqrt{n}$ Jan 27 '19 at 2:07
• @ paw88789 you are right, I edit it Jan 27 '19 at 2:09

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.

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.

• Weird.... Not sure how I duplicated my post. Jan 27 '19 at 2:42