Prime factorization - list

Question

I am trying to implement a function primeFac() that takes as input a positive integer n and returns a list containing all the numbers in the prime factorization of n.

I have gotten this far but I think it would be better to use recursion here, not sure how to create a recursive code here, what would be the base case? to start with.

My code:

def primes(n):     primfac = []     d = 2     while (n > 1):          if n%d==0:              primfac.append(d)     # how do I continue from here... ? 

Answer 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).