2
$\begingroup$

Can someone give me the proper intuition as to why it is sufficient to check up to $\sqrt{n}$ to find out if $n$ is a prime number?

$\endgroup$
2
  • 4
    $\begingroup$ because if $n$ factors into two or more terms, group them into two factors: then either they are both $=\sqrt n$ or one is higher and the other is lower, thus it is sufficient to find (or not) the lower. $\endgroup$
    – G Cab
    Mar 27, 2017 at 17:56
  • $\begingroup$ @G_Cab thanks for the help $\endgroup$
    – Ayan Shah
    Mar 27, 2017 at 18:09

2 Answers 2

1
$\begingroup$

If $n$ is composite, then at least one of its factors $\le\sqrt{n}$. If n is not divisible by any integer $\le\sqrt{n}$, then $n$ is prime.

$\endgroup$
0
$\begingroup$

First assume that two non-trivial factors are both greater than $\sqrt{n}$ , then their product is greater than $(\sqrt{n})^2=n$ , disproving that that they multiply to $n$ . The same hold if one factor is equal to $\sqrt{n}$ and the other is greater. We conclude that at least one factor must be lower than the square root. In that case a search up the square root will find such a factor.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .