SOLUTION: I would appreciate help with this question please. Checking to see whether the number p is prime or not. Is it enough to test that p does not have any divisors ≤ square roo

Algebra ->  Divisibility and Prime Numbers -> SOLUTION: I would appreciate help with this question please. Checking to see whether the number p is prime or not. Is it enough to test that p does not have any divisors ≤ square roo      Log On


   

Question 871159: I would appreciate help with this question please.
Checking to see whether the number p is prime or not.
Is it enough to test that p does not have any divisors ≤ square root of p.

Answer by Edwin McCravy(20065) About Me  (Show Source):
You can put this solution on YOUR website!
Yes because suppose p has a factor q > sqrt%28p%29

and you have tried all the numbers less than sqrt%28p%29. 

Then p%2Fq would also be a factor of p

and p%2Fq < p%2Fsqrt%28p%29 = p%2Asqrt%28p%29%2Fp = sqrt%28p%29

so you would already have found the factor p%2Fq since it is less
than sqrt%28p%29 and you would have known that p was not prime.  So
there would be no use to try q.

Edwin