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

[Ian Kelly]

On Tue, Jun 21, 2011 at 3:09 PM, John Salerno <johnjsal at gmail.com> wrote:
> Don't worry, I was still unclear about what to do after reading all
> the responses, even yours! But one thing that made me feel better was
> that I wasn't having a Python problem as much as a *math* problem. I
> changed my get_factors function to only go as far as the square root
> of the number in question, and that yielded an answer immediately. :)
>
> 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.

Careful, note that the greatest prime factor may actually be greater
than the square root.  It's just that it's possible to find it without
iterating past the square root.  This is because for each p that is a
factor of n, q is also a factor of n, where p * q = n.  If p >
sqrt(n), then q < sqrt(n).  Therefore you can find p by finding q and
dividing n / q.