if $n\in\mathbb{N}$ and $n \mod 2,..., n\mod \text{floor}\sqrt{n}\neq 0$ then $n$ is prime

Question

This was an algorithm to see whether a number is prime or not, but what is the justification. Why is it sufficient to check all number from $2$ to $\text{floor}\sqrt{n}$?

Answer 1

If you go through all numbers from $2$ to $m$ where $m$ is the biggest $m^2 \le n$ you will either find a number divisible by $n$ or you will not find it.

If you do, $n$ is not prime. If you don't, $n$ is prime, otherwise $n = k \cdot m$ for some $k$ and $m$ where $k^2 > n$ and $m^2 > n$, i.e. $k \cdot m > n$.

Therefore it's enough to check all numbers from $2$ to $\lfloor \sqrt{n} \rfloor$.

We say that the time complexity of the algorithm is $O(\sqrt{n})$.

For primes we can make it even better if we keep prior primes in memory. For that, we can go through only prime numbers, not through all numbers.

In practice this does not make sense if we need to figure out whether some number prime or not. But it does if we need to find all primers up to some value.

If we use memory, then the time complexity will be $O\left(\frac{\sqrt{n}}{ln(\sqrt{n})}\right)$ for each n up to some number $N$, but we need $O\left(\frac{N}{ln(N)}\right)$ for memory.

Answer 2

It's a test to see if any $n$ has any divisors. If $n\pmod k \equiv 0$ then $k|n$ and $n$ is not prime.

So $n\pmod k \not \equiv 0$ for all $k \le \sqrt n$ means that $n$ has no divisors less than or equal to the square root of $n$.

But why is that enough to know it has no divisors other divisors (other than $1$ and itself)?

Well if $m|n$ then $k= \frac nm$ is an integer and $k*m = n$ and so $k$ is also a divisor. But if and $m > \sqrt n$ then $k = \frac nm < \frac n{\sqrt n} = \sqrt n$. So if $m$ is a divisor that is larger than $\sqrt n$, the $k = \frac mn$ is a divisor of $n$ that is less than $\sqrt n$. (and vice versa).

Is if $n$ has a divisor $k$ that is $\le \sqrt n$, then $n$ will have a divisor $ m = \frac nk$ that is $\ge \sqrt n$. And if $n$ does have any divisors that are $\le \sqrt n$, then $n$ will not have any divisors (other than $1$ and $n$ itself) that or $\ge \sqrt n$.

So if $n\pmod k \not \equiv 0$ for all $k \le \sqrt n$ then $n$ has no divisors less than or equal to $\sqrt n$ AND THEREFORE $n$ has no divisors between $\sqrt n$ and $n$. Between $1$ and $n$, if the test passes, there are not divisors of $n$.

So the only divisors of $n$ are $1$ and $n$.

In other words.... $n$ is prime.

Answer 3

Suppose $n$ has a nontrivial divisor greater than $\sqrt n$, call it $d_2$. This means that $$\frac{n}{d_2}$$ is an integer. Furthermore, $$\frac{n}{d_2} < \sqrt n.$$

And since there usually are fewer numbers between $1$ and $\sqrt n$ than between $\sqrt n$ and $n$, it is usually quicker to check the former than the latter.

Here's a concrete example: is $2947$ prime? It's not, but you don't know that yet. We see that $\sqrt{2947} \approx 54.28627819$. Do you want to check the divisibility of $2947$ by the numbers $2$ to $54$ or by the numbers $56$ to $2946$? I think you would pick the former.

Even better, check the numbers $2$ and the odd numbers $3$ to $53$ (because if $2947$ is not divisible by $2$, it's not going to be divisible by $54$ either).

And so, we find that $2947 = 7 \times 421$. It probably would have been much faster for you to find $7$ first than it would have been to find $421$ first.