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.

up vote 2 down vote accepted

Your result is incorrect:

>>> 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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.