Why do we check up to the square root of a prime number to determine if it is prime?
If a number n
is not a prime, it can be factored into two factors a
and b
:
n = a * b
Now a
and b
can't be both greater than the square root of n
, since then the product a * b
would be greater than sqrt(n) * sqrt(n) = n
. So in any factorization of n
, at least one of the factors must be smaller than the square root of n
, and if we can't find any factors less than or equal to the square root, n
must be a prime.
Let's say m = sqrt(n)
then m × m = n
. Now if n
is not a prime then n
can be written as n = a × b
, so m × m = a × b
. Notice that m
is a real number whereas n
, a
and b
are natural numbers.
Now there can be 3 cases:
- a > m ⇒ b < m
- a = m ⇒ b = m
- a < m ⇒ b > m
In all 3 cases, min(a, b) ≤ m
. Hence if we search till m
, we are bound to find at least one factor of n
, which is enough to show that n
is not prime.
Because if a factor is greater than the square root of n, the other factor that would multiply with it to equal n is necessarily less than the square root of n.