John Salerno <johnj...@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.
--
http://mail.python.org/mailman/listinfo/python-list
