# Why is my code faster with append() in a loop than with a large list?

Piet van Oostrum piet at cs.uu.nl
Mon Jul 6 17:15:47 CEST 2009

```>>>>> Dave Angel <davea at dejaviewphoto.com> (DA) wrote:

>DA> It would probably save some time to not bother storing the zeroes in the
>DA> list at all.  And it should help if you were to step through a list of
>DA> primes, rather than trying every possible int.  Or at least constrain
>DA> yourself to odd numbers (after the initial case of 2).

The first and the last save a constant factor (slightly less than 2):

def factorise(num):
"""Returns a list of prime factor powers. For example:
factorise(6) will return
[2, 2] (the powers are returned one higher than the actual value)
as in, 2^1 * 3^1 = 6."""
powers = []
factor = 2
while num > 1:
power = 0
while num % factor == 0:
power += 1
num /= factor
if power > 0:
powers.append(power+1)
factor += 1
return powers

...
return reduce(mul, powers)

or to skip the odd factors:

def factorise(num):
"""Returns a list of prime factor powers. For example:
factorise(6) will return
[2, 2] (the powers are returned one higher than the actual value)
as in, 2^1 * 3^1 = 6."""
powers = []
factor = 2
while num > 1:
power = 0
while num % factor == 0:
power += 1
num /= factor
if power > 0:
powers.append(power+1)
factor = 3 if factor == 2 else factor + 2
return powers

This can be slightly optimised by taking factor 2 out of the loop.

def factorise(num):
"""Returns a list of prime factor powers. For example:
factorise(6) will return
[2, 2] (the powers are returned one higher than the actual value)
as in, 2^1 * 3^1 = 6."""
powers = []
power = 0
while num % 2 == 0:
power += 1
num /= 2
if power > 0:
powers.append(power+1)
factor = 3
while num > 1:
power = 0
while num % factor == 0:
power += 1
num /= factor
if power > 0:
powers.append(power+1)
factor += 2
return powers

To restrict the search to primes you would have to use a
sieve of Eratosthenes or something similar.
My first attempt (with a sieve from
http://code.activestate.com/recipes/117119/) only gave a speed decrease!!
But this had the sieve recreated for every triangle number. A global
sieve that is reused at each triangle number is better. But the speed
increase relative to the odd factors only is not dramatical.

# Based upon http://code.activestate.com/recipes/117119/

D = {9: 6} # contains composite numbers
Dlist = [2, 3] # list of already generated primes

def sieve():
'''generator that yields all prime numbers'''
global D
global Dlist
for p in Dlist:
yield p
q = Dlist[-1]+2
while True:
if q in D:
p = D[q]
x = q + p
while x in D: x += p
D[x] = p
else:
Dlist.append(q)
yield q
D[q*q] = 2*q
q += 2

def factorise(num):
"""Returns a list of prime factor powers. For example:
factorise(6) will return
[2, 2] (the powers are returned one higher than the actual value)
as in, 2^1 * 3^1 = 6."""
powers = []
power = 0
for factor in sieve():
power = 0
while num % factor == 0:
power += 1
num /= factor
if power > 0:
# if you really want the factors then append((factor, power))
powers.append(power+1)
if num == 1:
break
return powers

--
Piet van Oostrum <piet at cs.uu.nl>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email: piet at vanoostrum.org

```

More information about the Python-list mailing list