Prime factorization - list

Solution 1:

A simple trial division:

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

with O(sqrt(n)) complexity (worst case). You can easily improve it by special-casing 2 and looping only over odd d (or special-casing more small primes and looping over fewer possible divisors).

Solution 2:

This is a comprehension based solution, it might be the closest you can get to a recursive solution in Python while being possible to use for large numbers.

You can get proper divisors with one line:

divisors = [ d for d in xrange(2,int(math.sqrt(n))) if n % d == 0 ]

then we can test for a number in divisors to be prime:

def isprime(d): return all( d % od != 0 for od in divisors if od != d )

which tests that no other divisors divides d.

Then we can filter prime divisors:

prime_divisors = [ d for d in divisors if isprime(d) ]

Of course, it can be combined in a single function:

def primes(n):
    divisors = [ d for d in range(2,n//2+1) if n % d == 0 ]
    return [ d for d in divisors if \
             all( d % od != 0 for od in divisors if od != d ) ]

Here, the \ is there to break the line without messing with Python indentation.

Solution 3:

The primefac module does factorizations with all the fancy techniques mathematicians have developed over the centuries:

#!python

import primefac
import sys

n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))