On Mon, Nov 8, 2010 at 23:49, Richard D. Moores <rdmoo...@gmail.com> wrote:
> On Mon, Nov 8, 2010 at 22:47, Richard D. Moores <rdmoo...@gmail.com> wrote:
>> On Mon, Nov 8, 2010 at 21:31, Richard D. Moores <rdmoo...@gmail.com> wrote:
>>
>>> 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.
>
> Dick
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)
Take a look at the difference in speed his suggestion made, and the
larger n is, the greater the difference:
<http://tutoree7.pastebin.com/S8AbyR66>
At n = 100,000,000 the speed improvement over the fastest of the other
3 versions was 2579x!
Employing append() instead of extend() as here:
def proper_divisors_sum(n):
pd_list = []
for x in range(1, int(n**.5)+1):
if n % x == 0:
factor = int(x)
pd_list.append(factor)
factor2 = int(n/factor)
pd_list.append(factor2)
pd_list = list(set(pd_list))
pd_list.sort()
pd_list = pd_list[:-1]
return sum(pd_list)
improves speed by 20% or 30% for large n, but I didn't paste those results.
I'll begin a new thread soon to ask for advice on optimizing a script
that finds amiable pairs, and of course employs proper_divisors_sum().
Dick
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
