Prime number algorithm

1. Jul 30, 2004

split

When trying to determine whether a number is prime or not, the following algorithm is often used: Test all numbers up to [sqrt[n]] ([x] is the ceiling of x) to see if any divide evenly into n. If any do, the number is not prime.

My question is, why do you only have to test up to [sqrt[n]]? How does that work mathematically?

2. Jul 30, 2004

split

3. Jul 31, 2004

shmoe

If an integer n is composite, then you can factor it n=ab where a and b are both integers greater than 1. We can't have both a>sqrt(n) and b>sqrt(n), otherwise we'd get n>n. If a<=sqrt(n) then any prime dividing a (and we know there's at least one) is a prime factor of n that's less than sqrt(n). If b<=sqrt(n), we likewise get a prime factor of n less than sqrt(n). So if n is composite, it always has a prime factor <=sqrt(n), and it's enough to check these to verify whether n is composite or not.

4. Aug 1, 2004

Dburghoff

Furthermore, you don't have to test every number up to the sqrt(n), just 2 and all of the odd ones.