> > ------------------------------ > > Message: 2 > Date: Tue, 09 Nov 2010 12:35:26 +0100 > From: Stefan Behnel <stefan...@behnel.de> > To: tutor@python.org > Subject: Re: [Tutor] List comprehension question > Message-ID: <ibbblu$58...@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
_______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
