Why do we check up to the square root of a prime number to determine if it is prime?

Question

To test whether a number is prime or not, why do we have to test whether it is divisible only up to the square root of that number?

Solution 1

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.

Solution 2

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:

1. a > m ⇒ b < m
2. a = m ⇒ b = m
3. 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.

Solution 3

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.

Solution 4

Suppose n is not a prime number (greater than 1). So there are numbers a and b such that

n = ab      (1 < a <= b < n)

By multiplying the relation a<=b by a and b we get:

a^2 <= ab
 ab <= b^2

Therefore: (note that n=ab)

a^2 <= n <= b^2

Hence: (Note that a and b are positive)

a <= sqrt(n) <= b

So if a number (greater than 1) is not prime and we test divisibility up to square root of the number, we will find one of the factors.

Solution 5

It's all really just basic uses of Factorization and Square Roots.

It may appear to be abstract, but in reality it simply lies with the fact that a non-prime-number's maximum possible factorial would have to be its square root because:

sqrroot(n) * sqrroot(n) = n.

Given that, if any whole number above 1 and below or up to sqrroot(n) divides evenly into n, then n cannot be a prime number.

Pseudo-code example:

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}

View more solutions

Comments

[anukalp]

n = 12 m = sqrt(12) = 3.46, a = 2, b = 6. n = mm i.e. 12=3.46*3.46 and n = ab i.e 12=2*6. Now condition 3. a < m < b i.e 2 < 3.46 < 6. So to check prime we only need to check for number less than 3.46 which is 2 to find out that number is not prime. Hence, check divisibility by numbers less than or equal to(if n = 4, m=a=b=2) square root of n.

[Huei Tan]

I think we should highlight the assumption first. Assume n is not a prime, and the prove it, otherwise it's a prime.

[Jon M]

Actually, I'm not convinced it is a better answer. It is a correct answer, but it doesn't really answer the question. It just describes some other dynamics around primes and the sqrt. @Sven's answers is both succinct, and doesn't create more questions in the process.

[Adrian]

Brilliant observation. Using this observation to create a guard statement in Swift in conjunction with this handy stackoverflow.com/a/25555762/4475605 to do an early exit from a calculation rather than wasting computational power. Thank you for posting.

[Super Cat]

@Adrian I must confess that after coming back to this answer, I did find an error at the time of your posting. You cannot perform division on a 0, and in theory if you could ++i would become the number 1, which would always return false (because 1 divides into everything). I've corrected the answer above.

[Adrian]

Yep...I addressed that in my code...your square root observation is a great way to throw out a non-prime value early before you begin running calculations. I was getting killed on a big number that turned out to be a big waste of time. I also learned this algorithm can substantially reduce processing times on big numbers, too. en.wikipedia.org/wiki/Miller–Rabin_primality_test

[Thierry Lathuille]

There are much shorter and IMHO much easier to understand and more on-topic explanations in the comments and the 6 years old answers...

[daGo]

b & c <= Math.sqrt(n)?; It should be rather b || c ( b or c) since if n=6, b=3, c=2 then Math.sqrt(n) > c.

[daGo]

If you curious why it is true @LoMaPh explained the fact in its answer greatly. I added my answer because I had really hard times to visualize and understand other provided answers. It just didn't clicked.

[Will Ness]

I rolled back to the last good version. you missed it when someone needlessly removed a word ('hence'), which is needed for the flow.

[Admin]

Thanks buddy for the correction. doing the correction. :)

[Benoît]

How does sqrt(n) have to be precise enough for this property to hold given that we are using floating points.

[Sven Marnach]

@Benoît You can always use the check i * i <= n instead of i <= sqrt(n) if you want to avoid the intricacies of floating-point numbers.

[gnasher729]

Since it doesn't hurt (except for sometimes an additional division) to check one more divisor, you can just calculate ceil(sqrt(n)).

[Sven Marnach]

@gnasher729 In some cases this might be useful, but this all heavily depends on implementation details (programming language, hardware, data types, libraries), none of which are known in this general consideration.

[Tony]

Mate i trully believe that this is the correct answer. Everyone says about a=b*c but they dont mention that b & c are primes. So I was trying to figure out the answer and as you said, didnt click. Until i found your answer that makes everything clear! Thank you so much for this! Otherwhise, for the whole day I would have this question in my head!

[Will Ness]

useful or not, what @gnasher729 had proposed is never hurtful, and costs almost nothing. better safe than sorry.

[Sven Marnach]

@WillNess Even ceil(sqrt(n)) may not be enough depending on environment, e.g. when the floating-point type doesn't have enough precision to represent sqrt(n) even if it's an integer (which in practice would probably mean that you can't check all numbers up to sqrt(n) anyway). I just feel there are too many unknowns here. The approach of checking i * i <= n should always work, though.

[Will Ness]

except for the overflow. :) i <= n / i probably doesn't have this problem.

[aderesh]

I like this answer better than the accepted answer - the accepted answer does not explain well why a and b both cannot be greater than sqrt(n). 3 cases made it clear to me.

[Rohan Devaki]

explain with an example , this is not at all understandable

[Rohan Devaki]

awesome explaination, thanks