0

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

S.S.Danyal
  • 667
Pratyush Kumar
  • 37
  • 3
    Actually till $\sqrt{n}$ is enought. – S.S.Danyal Jan 27 '19 at 01:18
  • How so??If I could get the result mathematically – Pratyush Kumar Jan 27 '19 at 01:20
  • 1
    @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. – Jack D'Aurizio Jan 27 '19 at 01:23
  • This link should help... – Eleven-Eleven Jan 27 '19 at 01:23
  • Suppose $n$ is not prime and the smallest prime that divides $n$ is $>\sqrt{n}$ – saulspatz Jan 27 '19 at 01:23
  • Why would you check odd numbers? Why not even numbers? If $k$ is a composite number (whether odd nor even) and it divides $n$ then $k$'s prime factors divid $n$ and you would have already found them. Since the primes didn't already work, then $k$ will not work. If $2,3$ and $5$ didn't divide $n$ then there is no reason to check $15$. $15$ won't work because $3$ didn't work. – fleablood Jan 27 '19 at 02:57
  • I’m voting to close this question because the given answer is perfect. – Kurt G. Jan 20 '24 at 11:10

2 Answers2

0

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)

S.S.Danyal
  • 667
0

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.

fleablood
  • 124,253