Finding the prime number $n$: why checking for a divisor between 2 and $\lfloor \frac{n}{2} \rfloor$ is enough?

Question

Let's say I want to check whether 33 (say $n$) is a prime number or not. Instead of checking whether 33 is divisible by a number between 2 and 31 or not, it is sufficient enough to verify that 33 is divisible by a number between 2 and 15 ($\lfloor \frac{31}{2} \rfloor$). I wrote a program, and it worked fine. Why half the size of the number is sufficient enough? How can you make sure that the divisor does not lie between $\frac{n}{2}$ and $n - 1$.

Answer 1

This works because a number $n$ can have no divisor $d$ with $\frac{n}2<d<n$ - that is, we're not checking that range because we already know that there's nothing to see in it. This is because, if $d$ is in that range, then every positive multiple of it is greater than $n$ - that is, $n<2d<3d<4d<5d<\ldots$. Obviously, this precludes $n$ being a multiple of $d$ (which is equivalent to saying $d$ is a divisor of $n$).

This said, the more standard and efficient bound is to check for divisors $d$ only in the range $1<d \leq\sqrt{n}$, which gives more efficiency than using $\frac{n}2$ as the upper bound. There can be divisors between $\sqrt{n}$ and $n$, however, if $d$ is a divisor of $n$ in that range, then $\frac{n}d$ is a divisor of $n$ less than $\sqrt{n}$. That is to say that, if there are any divisors, there must be one no larger than $\sqrt{n}$.

Answer 2

It is quite simple.

When a number is written as a set of factors a x b. And all possible products are written, a keeps on increasing an b keeps on decreasing. After that b takes on all the values of a.

Let's say a number has a factor greater than n/2. Remember n/2 has to be multiplied with 2 to give n. Any number more than n/2 has to be multiplied with a number less than 2, to give n. And, the only such factor is 1*n.

It is more efficient to check till the square root of n. If a number has a factor greater than its square root, then that factor must be multiplied with a number less than square root of n to give n. However, that lesser factor has already been checked off. A number cannot be the product of two numbers, both greater than its square root.

I recommend you store the value of its square root, rather than call the square root function every time in the loop.

Answer 3

We can prove it.

Consider a number $n \in \mathbb{N^+}$ that can be factored as $n = a\times b$. Without loss of generality it can be assumed that $a \geq b$.

Consider the factor $a = \frac{n}{b}$. Assume that $a\geq \frac{n}{2}$.

Then $\frac{n}{b} \geq \frac{n}{2} \Rightarrow b\leq 2$.

So if $a \geq\frac{n}{2}$, then $b \in \{1,2\}$.

Check the case that $b = 1$. Then $a = n$.

Check the case that $b =2$. Then $a=\frac{n}{2}$.

So given that a factor $a \geq \frac{n}{2}$, then $a = \frac{n}{2}$ or $a = n$.