[Tutor] List comprehension question

Richard D. Moores rdmoores at gmail.com
Tue Nov 9 14:41:51 CET 2010


On Tue, Nov 9, 2010 at 03:35, Stefan Behnel <stefan_ml at behnel.de> wrote:
> Richard D. Moores, 09.11.2010 12:07:
>>>>>
>>>>> 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>.
>>>>
>>>> NO! Use  int(n/2)+1 .  I'll correct that in
>>>> <http://tutoree7.pastebin.com/dyRC8vuX>  and report back.
>>>
>>> See<http://tutoree7.pastebin.com/eZPaVpwG>
>>>
>>> But now I'll have to redo again using Stefan's ingenious suggestion.
>>
>> Here's what I wrote using Stefan's suggestion:
>>
>> def proper_divisors_sum(n):
>>     pd_list = []
>>     for x in range(1, int(n**.5)+1):
>>         if n % x == 0:
>>             factor = int(x)
>>             factor2 = int(n/factor)
>>             pd_list.extend([factor, factor2])
>>     pd_list = list(set(pd_list))
>>     pd_list.sort()
>>     pd_list = pd_list[:-1]
>>     return sum(pd_list)
>
> Have a look at divmod():
>
> http://docs.python.org/library/functions.html#divmod
>
> Note that you don't need to convert 'x' to an int. It already has that type
> (see the docs on range()). Also, int(n/factor) is the same as n//factor
> here.

>From your suggestions I made 2 versions:

def proper_divisors_sum1(n):
    pd_list = []
    for x in range(1, int(n**.5)+1):
        quotient, remainder = divmod(n, x)
        if remainder == 0:
            pd_list.append(x)
            pd_list.append(quotient)
    pd_list = list(set(pd_list))
    pd_list.sort()
    pd_list = pd_list[:-1]
    return sum(pd_list)

def proper_divisors_sum2(n):
    pd_list = []
    for x in range(1, int(n**.5)+1):
        if n % x == 0:
            pd_list.append(x)
            pd_list.append(n//x)
    pd_list = list(set(pd_list))
    pd_list.sort()
    pd_list = pd_list[:-1]
    return sum(pd_list)

The first actually slowed down what I had before, but the second made
for a nice speed-up.

Thanks, Stephan.

Dick


More information about the Tutor mailing list