Prime number algorithm

[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?

[split]

I just experienced an extremely weird coincidence. I was reading sosmath.com's CyberBoard and this thread just happened to be in the algebra section:

http://www.sosmath.com/CBB/viewtopic.php?t=8884

[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.

[Dburghoff]

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