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

[Irmen de Jong]

On 21-6-2011 23:09, John Salerno wrote:
> On Jun 21, 3:22 pm, Irmen de Jong <ir... at -NOSPAM-xs4all.nl> wrote:
>> On 21-06-11 22:10, Irmen de Jong wrote:
>> [stuff]
>>
>> I didn't read the last paragraph of John's message until just now, and
>> now realize that what I wrote is likely way too much information for
>> what he asked.
>> I'm sorry. Next time I'll read everything until and including the last
>> full stop.
>>
>> Irmen
> 
> 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. :)

Ok, cool :)


> 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.

If there is an exact divisor d >= √n, then the quotient n/d is also a divisor of n, and
that quotient is <= √n. So if we don't find such a quotient before reaching √n, it's not
useful to search for d > √n (because no divisors would be found).

Irmen