PrimeFactorization.py by Michael Yaworski

This is a very well optimized version of my prime factorization algorithm in Python. The link to my old versions can be found here.

# reduces the parameter n into a product of only prime numbers
# and returns a list of those prime number factors
def primeFactorize(n):
    primeFactors = []
    primeFactor = 0
    i = 2

    while i <= n / i:
        if n % i == 0:
            primeFactor = i
            primeFactors.append(i)
            n /= i
        else:
            i += 1

    if primeFactor < n:
        primeFactors.append(int(n))
    else:
        primeFactors.append(primeFactor)

    return primeFactors

# example
print (primeFactorize(13195)) # [5, 7, 13, 29]
DOWNLOAD

             Created: October 10, 2014
Completed in full by: Michael Yaworski