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

algorithm primes primality-test
Pan picture Pan · Apr 28, 2011 · Viewed 152.9k times · Source

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?

Answer

Sven Marnach picture Sven Marnach · Apr 28, 2011

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.

Related questions

Determining if a given number is a prime in haskell

So I have devised the following function for seeing if a given number is a prime in Haskell (it assumes the first prime is 2): isPrime k = length [ x | x <- [2..k], k `mod` x == 0] == 1 it has the obvious pitfall …

Read More
Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More
Which is the fastest algorithm to find prime numbers?

Which is the fastest algorithm to find out prime numbers using C++? I have used sieve's algorithm but I still want it to be faster!

Read More