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?