Finding prime factors by taking the square root

If a number $N$ has a prime factor larger than $\sqrt{N}$ , then it surely has a prime factor smaller than $\sqrt{N}$.

So it's sufficient to search for prime factors in the range $[1,\sqrt{N}]$, and then use them in order to compute the prime factors in the range $[\sqrt{N},N]$.

If no prime factors exist in the range $[1,\sqrt{N}]$, then $N$ itself is prime and there is no need to continue searching beyond that range.


If you do not find a factor less than $\sqrt{x}$, then $x$ is prime for the following reason. Consider the opposite, you find two factors larger than $\sqrt{x}$, say $a$ and $b$. But then $a\cdot b> \sqrt{x}\sqrt{x} = x$. Therefore, if there is a factor larger than $\sqrt{x}$, there must also exist a factor smaller than $\sqrt{x}$, otherwise their product would exceed the value of $x$.

Regarding the last question. You will not miss some factor like $2\cdot n$ because you have already checked if $2$ is a factor.


What you're describing is a prime-testing algorithm known as the sieve of Eratosthenes.

It seems like you already understand the concept:

  • Cross out $1$

  • Circle $2$ as the first prime, then cross out all of the multiples of $2$ in your list.

  • The next not-crossed-out number is the next prime (in this case $3$).

If your list has $N$ numbers, you only need to test until you get to a prime that's bigger than $\sqrt{N}$.


Other users have mentioned the reason for $\sqrt{N}$ being the maximum you need to test until, but I'll add an alternative explanation. If you consider listing out all of the factors of $N$, in order from least to greatest, you will either get an even number or an odd number. $N$ has an odd number of factors if and only if it is a perfect square.

In any case, $N$ always has the same number of factors (strictly) less than its square root as it does (strictly) greater than its square root.

In fact, there's an explicit bijection between the set of factors less than $\sqrt{N}$ and the set of factors greater than $\sqrt{N}$ given by $$f(a) = \frac{N}{a}$$

(where $a$ is a factor of $N$ less than $\sqrt{N}$)