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

  • 3
    $\begingroup$ Actually till $\sqrt{n}$ is enought. $\endgroup$
    – S.S.Danyal
    Jan 27 '19 at 1:18
  • $\begingroup$ How so??If I could get the result mathematically $\endgroup$ Jan 27 '19 at 1:20
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 27 '19 at 1:23
  • $\begingroup$ This link should help... $\endgroup$ Jan 27 '19 at 1:23
  • $\begingroup$ Suppose $n$ is not prime and the smallest prime that divides $n$ is $>\sqrt{n}$ $\endgroup$
    – saulspatz
    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)

  • $\begingroup$ Ok...but why not all odd numbers till it's root rather than only prime numbers till it's root $\endgroup$ Jan 27 '19 at 1:41
  • $\begingroup$ 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. $\endgroup$
    – S.S.Danyal
    Jan 27 '19 at 1:52
  • $\begingroup$ Oo... thanks... $\endgroup$ Jan 27 '19 at 1:56
  • $\begingroup$ Should be $p\le \sqrt{n}$ $\endgroup$
    – paw88789
    Jan 27 '19 at 2:07
  • $\begingroup$ @ paw88789 you are right, I edit it $\endgroup$
    – S.S.Danyal
    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.

====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.

  • $\begingroup$ Weird.... Not sure how I duplicated my post. $\endgroup$
    – fleablood
    Jan 27 '19 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.