To find whether $a$ is a prime number

I have been using this rule to determine whether a number is a prime number, but not how to prove it. Why it has to be $\sqrt{a}$?

If $a$ is not divisible by all the prime numbers less than or equal to $\sqrt{a}$, then $a$ is a prime number.

Solution 1:

Assume $a$ is not a prime number. Then it can be written as $a = bc$ with $b, c \ge 2$. Then the smaller of $b, c$ is less than or equal to $\sqrt a$, for otherwise the product would be greater than $\sqrt a \, \sqrt a = a$. This smaller factor is then either a prime itself or has a prime factor that is even smaller.

Solution 2:

Divisors come in pairs. If $n$ divides $a$, so does $a/n$, as $\sqrt{a}\sqrt{a}=a$, one of the factors in a pair must be smaller than or equal to $\sqrt{a}$.

Solution 3:

Just another point of view

Suppose that $a$ is divisible by a prime $p$. This means that: $$a = p \cdot k \Rightarrow p = \frac{a}{k}.$$ Moreover, suppose that $p > \sqrt{a}$, then:

$$\frac{a}{k} > \sqrt{a} \Rightarrow k < \sqrt{a}.$$

This means that I can only use the primes $p \in [\sqrt{a}, a]$ to determine if $a$ is prime, instead of the set $[0, \sqrt{a}]$.

Which is the set that best suits for the algorithm?

I guess the smallest, since you will have a smaller number of primes to be tested. The set $[\sqrt{a}, a]$ has length $a-\sqrt{a}$, while the set $[0, \sqrt{a}]$ has length $\sqrt{a}$.

Notice that: $$\sqrt{a} < a-\sqrt{a} \Rightarrow 2\sqrt{a} < a \Rightarrow \sqrt{a} > 2 \Rightarrow a > 4.$$

In general, you want test a number $a$ bigger than $4$. For this reason, you just look to the set $[0, \sqrt{a}]$... it is just faster!

Example.

Take $a = 77$ and notice that $\sqrt{a} \simeq 8.78$. If you use the set $[0, \sqrt{a}]$, the you will have to check if $a$ is divisible by $3,5,7$ (only three numbers). On the other hand, if you choose the set $[\sqrt{a}, a]$, you will have to check if $a$ is divisible by $11, 13, 17, 19, 23, 29, 31, 37, ...$. Hey, this is too much, no?!

Solution 4:

Let $ab=p$ where $a,b$ are possible factors of prime candidate $p$.

If you find a factor $b \geq \sqrt{p}$, then $a \leq \sqrt{p}$.

But if you checked all $a \leq \sqrt{p}$ and didn't find any factors ...