On 21-6-2011 23:09, John Salerno wrote: > On Jun 21, 3:22 pm, Irmen de Jong <ir...@-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 -- http://mail.python.org/mailman/listinfo/python-list
