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

[John Salerno]

On Jun 21, 4:41 pm, Ian Kelly <ian.g.ke... at gmail.com> wrote:
> On Tue, Jun 21, 2011 at 3:09 PM, John Salerno <johnj... 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.

Oh! Now it makes sense! That first sentence helped to put it into
perspective, too. The Wikipedia page says more or less the same thing,
but this paragraph just made more sense to me. :)

Thanks for the all the advice everyone. Now I'm on to problem #4, and
I'm stumped again, but that's what's fun! :)