Find the prime factorization of a given natural number.

PrimeFactorize.py

# To implement: More efficient nextPrime method, clock to compute processing time.
# Oliver Benning, github.com/obenn

def nextPrime(divisor):
    breakout = False
    while not breakout:
        divisor += 1
        for i in range (divisor):
            if (divisor) % (i + 1) == 0:
                breakout = True
                break;
    return divisor;

def toString(divisor):
    out = str(input)+" = "
    for i in factors:
        out += str(i) + "^" + str(factors[i])
        if not i == divisor:
            out += " * "
    return(out)

input = int(input("What number would you like to prime factorize? \n"))
mod = input

divisor = 2
factors = {}

while mod > 1:
    if mod % divisor == 0:
        if divisor in factors.keys():
            factors[divisor]+=1
        else:
            factors[divisor] = 1
        mod = mod/divisor
        continue;
    divisor = nextPrime(divisor);

print(toString(divisor))

An interesting task would be to come up with a mathematical proof that nextPrime() works.