sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

[Paul Rubin]

John Salerno <johnjsal at gmail.com> writes:
> However, even after reading the Wikipedia page about prime numbers and
> trial division, I'm still a little unclear as to why the square root
> of the number is the upper bound of the range you need to check.

Suppose p is the smallest divisor of n, and p > sqrt(n).
("Divisor" here means p=1 doesn't count).

p being a divisor of n means there is some q such that n = pq.
That means q = n / p.

If p > sqrt(n) that means that q must be < sqrt(n).  But that
contradicts the claim that p is the smallest divisor.

So we know that if there is a divisor at all, it must be <= sqrt(n)
and if we don't find one by then, n must be prime.