prime number question

why is it that in many algorithms to test if a number is prime, using a brute force division, it only checks for divisors up to the square root of the number to be checked?

for example:

bool isprime(n){
for i from 2 to ceil(sqrt(n)){
if n%i==0: return false;}

return true;
}

http://en.wikipedia.org/wiki/Prime_sieve

>>1

Because a composite number will always have at least one prime factor less than its square root. (If it didn't, its factors would multiply to be bigger than it.)

Well say we have, A ,any number.

If we check to see that all numbers up to sqrt(A) do not divide A, then A must be prime.


Proof.

If B > Sqrt (A) and B|A then A = B.C some C, but then C|A.

Now C > sqrt (A) as C|A but then B.C > sqrt (A) . sqrt (A) = A contradiction.


Pretty simple proof there.

thanks, im dumb.

Don't call me gay, but I need some mary jay!

Marijuana MUST be legalized.