[Tutor] Need help with script for finding pairs of amicable numbers

[col speed]

>
> ------------------------------
>
> Message: 2
> Date: Tue, 09 Nov 2010 12:35:26 +0100
> From: Stefan Behnel <stefan_ml at behnel.de>
> To: tutor at python.org
> Subject: Re: [Tutor] List comprehension question
> Message-ID: <ibbblu$58i$1 at dough.gmane.org>
> Content-Type: text/plain; charset=UTF-8; format=flowed
>
> 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)
>
>
>
>
>
> ---------------------
> Just a thought, but maybe getting the sums using prime factors would be a
> bit faster?

Get the prime factors with their powers. Add 1 to the power and subtract 1
from that. Then divide that by the factor minus 1. multiply that by the next
factor. An example is easier:

Take 1800, it's prime factors are - 2**3, 3**2, 5**2. So we do:
((2**4-1)/1) * ((3**3-1)/2) * ((5**3-1)/4) = (15*26*124)/8 = 1800

I have a couple of programmes ( stolen from the internet) that work out the
prime factors quite quickly, if you are interested.

Regards
Colin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20101110/cd4f85c2/attachment.html>