from math import floor def factors(n): result = [] for i in range(2,n+1): # test all integers between 2 and n s = 0; while n/i == floor(n/float(i)): # is n/i an integer? n = n/float(i) s += 1 if s > 0: for k in range(s): result.append(i) # i is a pf s times if n == 1: return result # test print factors(90)The result will be

[2, 3, 3, 5]This means that 90 is equal to 2*3*3*5.

from itertools import chain

ReplyDeletedef factors2(n):

result = []

# test 2 and all of the odd numbers

# xrange instead of range avoids constructing the list

for i in chain([2],xrange(3,n+1,2)):

s = 0

while n%i == 0: #a good place for mod

n /= i

s += 1

result.extend([i]*s) #avoid another for loop

if n==1:

return result

Results in a bit of a speedup

In [2]: timeit factors(1234567)

1 loops, best of 3: 674 ms per loop

In [3]: timeit factors2(1234567)

1000 loops, best of 3: 1.69 ms per loop

Bah, looks like comments on blogspot can't use pre tags,

ReplyDeleteI made a gist here

Works on 90, but when I call factors(15) it returns None, instead of [3, 5]. Seems to work on many numbers, but not all.

ReplyDeleteAlso works on '15' and other numbers when the 'while' statement is changed to:

ReplyDeletewhile n/float(i) == floor(n/float(i)): # is n/i an integer?