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

User · Answer

So to check whether a number N is Prime or not. We need to only check if N is divisible by numbers<=SQROOT(N). This is because, if we factor N into any 2 factors say X and Y, ie. N=XY. Each of X and Y cannot be less than SQROOT(N) because then, XY < N Each of X and Y cannot be greater than SQROOT(N) because then, X*Y > N

Therefore one factor must be less than or equal to SQROOT(N) ( while the other factor is greater than or equal to SQROOT(N) ). So to check if N is Prime we need only check those numbers <= SQROOT(N).

User · Answer

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  lt  m a   m   b   m a  lt  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

User · Answer

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

User · Answer

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  lt   sqrroot n       if  n   i    0          is prime   false      exit while          i

User · Answer

Let s say we have a number  a   which is not prime  not prime composite number means - a number which can be divided evenly by numbers other than 1 or itself  For example  6 can be divided evenly by 2  or by 3  as well as by 1 or 6     6   1    6  or  6   2    3  So now if  a  is not prime then it can be divided by two other numbers and let s say those numbers are  b  and  c   Which means   a b c   Now if  b  or  c    any of them is greater than square root of  a  than multiplication of  b   amp   c  will be greater than  a     So   b  or  c  is always  lt   square root of  a  to prove the equation  a b c    Because of the above reason  when we test if a number is prime or not  we only check until square root of that  number

User · Answer

Let s suppose that the given integer N is not prime   Then N can be factorized into two factors a and b     2  lt   a  b  lt  N such that N   a b  Clearly  both of them can t be greater than sqrt N  simultaneously    Let us assume without loss of generality that a is smaller   Now  if you could not find any divisor of N belonging in the range  2  sqrt N    what does that mean   This means that N does not have any divisor in  2  a  as a  lt   sqrt N     Therefore  a   1 and b   n and hence By definition  N is prime        Further reading if you are not satisfied   Many different combinations of  a  b  may be possible  Let s say they are    a1  b1    a2  b2    a3  b3            ak  bk   Without loss of generality  assume ai  lt  bi  1 lt   i  lt  k   Now  to be able to show that N is not prime it is sufficient to show that none of ai can be factorized further  And we also know that ai  lt   sqrt N  and thus you need to check till sqrt N  which will cover all ai  And hence you will be able to conclude whether or not N is prime

User · Answer

Any composite number is a product of primes   Let say n   p1   p2  where p2  gt  p1 and they are primes   If n   p1     0 then n is a composite number   If n   p2     0 then guess what n   p1     0 as well   So there is no way that if n   p2     0 but n   p1     0 at the same time  In other words if a composite number n can be divided evenly by p2 p3   pi  its greater factor  it must be divided by its lowest factor p1 too  It turns out that the lowest factor p1  lt   Math square n  is always true

User · Answer

Suppose n is not a prime number  greater than 1   So there are numbers a and b such that  n   ab       1  lt  a  lt   b  lt  n    By multiplying the relation a lt  b by a and b we get   a 2  lt   ab  ab  lt   b 2   Therefore   note that n ab   a 2  lt   n  lt   b 2   Hence   Note that a and b are positive   a  lt   sqrt n   lt   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

User · Answer

Yes  as it was properly explained above  it s enough to iterate up to Math floor of a number s square root to check its primality  because sqrt covers all possible cases of division  and Math floor  because any integer above sqrt will already be beyond its range   Here is a runnable JavaScript code snippet that represents a simple implementation of this approach     and its  quot runtime-friendliness quot  is good enough for handling pretty big numbers  I tried checking both prime and not prime numbers up to 10  12  i e  1 trillion  compared results with the online database of prime numbers and encountered no errors or lags even on my cheap phone    x000D   x000D  function isPrime num      if  num   2     0    num  lt  3     Number isInteger num         return num     2      else       const sqrt   Math floor Math sqrt num        for  let i   3  i  lt   sqrt  i    2          if  num   i     0            return false                    return true        x000D   lt label for  inp  gt Enter a number and click  Check    lt  label gt  lt br gt   lt input type  number  id  inp  gt  lt  input gt   lt button onclick  alert isPrime  document getElementById  inp   value     Prime     Not prime    type  button  gt Check  lt  button gt  x000D   x000D   x000D

User · Answer

Given any number n  then one way to find its factors is to get its square root p   sqrt n    p   Of course  if we multiply p by itself  then we get back n   p p   n   It can be re-written as   a b   n   Where p   a   b  If a increases  then b decreases to maintain a b   n  Therefore  p is the upper limit   Update  I am re-reading this answer again today and it became clearer to me more  The value p does not necessarily mean an integer because if it is  then n would not be a prime  So  p could be a real number  ie  with fractions   And instead of going through the whole range of n  now we only need to go through the whole range of p  The other p is a mirror copy so in effect we halve the range  And then  now I am seeing that we can actually continue re-doing the square root and doing it to p to further half the range

User · Answer

Let n be non-prime  Therefore  it has at least two integer factors greater than 1  Let f be the smallest of n s such factors  Suppose f   sqrt n  Then n f is an integer LTE sqrt n  thus smaller than f  Therefore  f cannot be n s smallest factor  Reductio ad absurdum  n s smallest factor must be LTE sqrt n

User · Answer

To test the primality of a number  n  one would expect a loop such as following in the first place     bool isPrime   true  for int i   2  i  lt  n  i         if n i    0           isPrime   false          break            What the above loop does is this   for a given 1  lt  i  lt  n  it checks if n i is an integer  leaves remainder 0   If there exists an i for which n i is an integer  then we can be sure that n is not a prime number  at which point the loop terminates  If for no i  n i is an integer  then n is prime     As with every algorithm  we ask   Can we do better    Let us see what is going on in the above loop    The sequence of i goes   i   2  3  4        n-1  And the sequence of integer-checks goes   j   n i  which is n 2  n 3  n 4        n  n-1    If for some i   a  n a is an integer  then n a   k  integer   or n   ak  clearly n   k   1  if k   1  then a   n  but i never reaches n  and if k   n  then a   1  but i starts form 2   Also  n k   a  and as stated above  a is a value of i so n   a   1    So  a and k are both integers between 1 and n  exclusive   Since  i reaches every integer in that range  at some iteration i   a  and at some other iteration i   k  If the primality test of n fails for min a k   it will also fail for max a k   So we need to check only one of these two cases  unless min a k    max a k   where two checks reduce to one  i e   a   k   at which point a a   n  which implies a   sqrt n    In other words  if the primality test of n were to fail for some i    sqrt n   i e   max a k    then it would also fail for some i  lt   n  i e   min a k    So  it would suffice if we run the test for i   2 to sqrt n

User · Answer

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

User · Answer

A more intuitive explanation would be  -  The square root of 100 is 10  Let s say a x b   100  for various pairs of a and b   If a    b  then they are equal  and are the square root of 100  exactly  Which is 10   If one of them is less than 10  the other has to be greater  For example  5 x 20    100  One is greater than 10  the other is less than 10   Thinking about a x b  if one of them goes down  the other must get bigger to compensate  so the product stays at 100  They pivot around the square root   The square root of 101 is about 10 049875621  So if you re testing the number 101 for primality  you only need to try the integers up through 10  including 10  But 8  9  and 10 are not themselves prime  so you only have to test up through 7  which is prime   Because if there s a pair of factors with one of the numbers bigger than 10  the other of the pair has to be less than 10  If the smaller one doesn t exist  there is no matching larger factor of 101   If you re testing 121  the square root is 11  You have to test the prime integers 1 through 11  inclusive  to see if it goes in evenly  11 goes in 11 times  so 121 is not prime  If you had stopped at 10  and not tested 11  you would have missed 11   You have to test every prime integer greater than 2  but less than or equal to the square root  assuming you are only testing odd numbers

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

Examples related to algorithm

Examples related to primes

Examples related to primality-test