## Monday, July 11, 2011

### Prime factor decomposition of a number

The following function compute the prime factors (PFs) of an integer.
```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.

1. from itertools import chain

def factors2(n):
result = []
# test 2 and all of the odd numbers
# xrange instead of range avoids constructing the list
for i in chain(,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 : timeit factors(1234567)
1 loops, best of 3: 674 ms per loop

In : timeit factors2(1234567)
1000 loops, best of 3: 1.69 ms per loop

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

3. 4. 