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