[Tutor] List comprehension question

[Richard D. Moores]

On Mon, Nov 8, 2010 at 03:43, Steven D'Aprano <steve at 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