>>>>> Dave Angel <(E-Mail Removed)> (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 <(E-Mail Removed)>

URL:

http://pietvanoostrum.com [PGP 8DAE142BE17999C4]

Private email:

(E-Mail Removed)