[Tutor] List comprehension question

[Stefan Behnel]

Richard D. Moores, 09.11.2010 06:31:
> On Mon, Nov 8, 2010 at 03:43, Steven D'Aprano 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.

Ah, good catch. Another lesson learned:

When you optimise, make sure you have good unit test coverage that proves 
you didn't break anything by trying to make things faster.

But Steven is right in that it's enough to run up to sqrt(n). You can 
improve things again by collecting not only the divisor you find but also 
its counterpart factor at the same time, i.e. when you find out that 2 is a 
divisor of n, add both 2 and n/2.

Then the point to stop is really sqrt(n).

Finally, sorting the resulting list will be a quick operation compared to 
finding the divisors.

Stefan