# Review my prime factorization function. Is it complete?

This is a function designed to return all the prime factors of a given number, in sorted order from least to greatest, in a list. It relies on another function that checks if a given number is prime. Here is the prime checking function:

def isPrime(x):
if x <= 1 or isinstance(x,float):
return False
else:
for divisor in range(2,x,1):
if x % divisor == 0:
return False
return True


Here is the prime factorization function:

def allPrimeFactors(y):
primeFactors = []
restart = True
while restart:
restart = False
for i in range(2,y,1):
if y % i == 0 and isPrime(i):
primeFactors.append(i)
y = y / i
if isPrime(y) and y == i:
primeFactors.append(y)
else:
pass
restart = True
else:
pass

primeFactors.sort()
return primeFactors


The while loop is designed to restart the for loop at the first iterable value, which is, in this case, 2. This is so that, if y factors into 2, or any other prime, more than once, it will appear in the final list more than once, how ever many times it, or any other prime, is part of the factorization of y. I found that, if a number's prime factorization was 2 primes of the same value, it would return an incomplete list, therefore I added the if statement to the end of the function so that if the final value of y was prime AND equal to the current value of i, it would append the final value of y to the end of the list, therefore making it complete.

This is a looping function I made to test the prime factorization function with a large set of numbers:

def primeFactorsTester(d,e):
for f in range(d,e+1,1):
if f == 1:
print "1 is undefined"
elif isPrime(f):
print str(f) + " is prime"
else:
print "the prime factors of " + str(f) + " are "+ str(allPrimeFactors(f))


It is meant to produce an output that is human readable, and is primarily a testing function.

Does my prime factorization function seem complete or incomplete? Any general feedback to give? I would love to know.

>>> allPrimeFactors(360)
[2, 2, 3, 3, 5]
>>> import operator
>>> reduce(operator.mul, allPrimeFactors(360), 1)
180


It is also unnecessarily complicated. The usual approach is, whenever you encounter a prime factor, extract as many powers of it as possible from the number. Here's another function that works:

def reallyAllPrimeFactors(n):
factors = []
for i in range(2, n + 1):
while n % i == 0:
factors.append(i)
n = n // i
return factors
>>> reallyAllPrimeFactors(360)
[2, 2, 2, 3, 3, 5]
>>> reduce(operator.mul, reallyAllPrimeFactors(360), 1)
360


Further optimizations to that are possible, but it is already much more efficient than your original. For one thing, it doesn't need to check any of its results for primality. (Why?)

• thank you, I guess I should be more rigorous in my testing. it seems the while loop is why it does not need to check any of it results for primality, because the while loop states while the condition n % i == o is true, it will add the value of i to the end of factors, then reset the value of n to be equal to n divided by i floored, and because while does not rely on a preset iterable sequence, when you get to a number that is not prime, the condition will no longer be true, I think, im not sure. – Arron Grier Oct 29 '13 at 1:57