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.

4 comments:

  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([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

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

    I made a gist here

    ReplyDelete
  3. 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.

    ReplyDelete
  4. Also works on '15' and other numbers when the 'while' statement is changed to:

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

    ReplyDelete