On Mon, Nov 8, 2010 at 03:43, Steven D'Aprano <st...@pearwood.info> wrote: > Richard D. Moores wrote:
> Coming back to your function: > > def proper_divisors(n): > sum_ = 0 > for x in range(1,n): > if n % x == 0: > sum_ += x > return sum_ > > > we can write that much more simply: > > def proper_divisors(n): > return sum(x for x in range(1, n) if n%x == 0) > > > And we can speed it up a bit by realising that there's no need to go all the > way up to n in the range. After all, we know that (say) 100%96 can't > possibly be zero. The largest factor of n is sqrt(n): > > > def proper_divisors(n): > return sum(x for x in range(1, int(math.sqrt(n))) if n%x == 0) > > > For large n, that will save a lot of time. That sqrt(n) works for speeding up the finding of primes, but here we want to use int(n/2) (and why didn't I think of that?), which results in about a 2x speedup. See <http://tutoree7.pastebin.com/dyRC8vuX>. Dick _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor