Python recursive program to prime factorize a number
-
06-07-2019 - |
Question
I wrote the following program to prime factorize a number:
import math
def prime_factorize(x,li=[]):
until = int(math.sqrt(x))+1
for i in xrange(2,until):
if not x%i:
li.append(i)
break
else: #This else belongs to for
li.append(x)
print li #First print statement; This is what is returned
return li
prime_factorize(x/i,li)
if __name__=='__main__':
print prime_factorize(300) #Second print statement, WTF. why is this None
Following is the output I get:
[2, 2, 3, 5, 5]
None
Altho', the returned value is printed properly, the after returned value seems to be printing none, all the time. What am I missing?
Also, how can I improve the program (continuing to use the recursion)
Solution
Your prime_factorize function doesn't have a return statement in the recursive case -- you want to invoke "return prime_factorize(x/i,li)" on its last line. Try it with a prime number (so the recursive call isn't needed) to see that it works in that case.
Also you probably want to make the signature something like:
def prime_factorize(x,li=None):
if li is None: li = []
otherwise you get wrong results when calling it two or more times:
>>> prime_factorize(10)
[2, 5]
>>> prime_factorize(4)
[2, 5, 2, 2]
>>> prime_factorize(19)
[2, 5, 2, 2, 19]
OTHER TIPS
If you want to do it completely recursive, I'd recommend this code, it does return the correct answer and the way it works is pretty clear. If you want to make the program as efficient as possible I'd recommend you to stick to one of your previous methods.
def primeFact (i, f):
if i < f:
return []
if i % f == 0:
return [f] + primeFact (i / f, 2)
return primeFact (i, f + 1)
This is a completely recursive way of solving your problem
>>> primeFact (300, 2)
[2, 2, 3, 5, 5]
>>> primeFact (17, 2)
[17]
>>> primeFact (2310, 2)
[2, 3, 5, 7, 11]
@Anthony's correctly answered your original question about print
. However, in the spirit of the several tips that were also offered, here's a simple refactorization using tail recursion removal:
def prime_factorize(x):
li = []
while x >= 2:
until = int(math.sqrt(x))+1
for i in xrange(2,until):
if not x%i:
li.append(i)
break
else:
li.append(x)
return li
x //= i
This doesn't address the crucial performance issues (big-O behavior is the same as for your original solution) -- but since Python itself doesn't do tail-recursion optimization, it's important to learn to do it manually.
"Change the [non-base-case] recursive steps 'return thisfun(newargs)'
into args=newargs; continue
and put the whole body into a while True:
loop" is the basic idea of tail-recursion optimization. Here I've also made li a non-arg (no reason for it to be an arg), put a condition on the while
, and avoided the continue
since the recursive step was at the end of the body anyway.
This formulation would be a good basis from which to apply further optimizing refactorings (sqrt avoidance, memoization, ...) to reach towards better performance.
A more functional-style version.
def prime_factorize( number ):
def recurse( factors, x, n ):
if x<2: return factors # 0,1 dont have prime factors
if n > 1+x**0.5: # reached the upper limit
factors.append( x ) # the only prime left is x itself
return factors
if x%n==0: # x is a factor
factors.append( n )
return recurse( factors, x/n, n )
else:
return recurse( factors, x, n+1 )
return recurse( [], number, 2)
for num, factors in ((n, prime_factorize( n )) for n in range(1,50000)):
assert (num==reduce(lambda x,y:x*y, factors, 1)), (num, factors)
#print num, ":", factors
def primeFactorization(n):
""" Return the prime factors of the given number. """
factors = []
lastresult = n
while 1:
if lastresult == 1:
break
c = 2
while 1:
if lastresult % c == 0:
break
c += 1
factors.append(c)
lastresult /= c
return factors
is it fine.