#!/bin/env python
#
# Simple python code for brute-force factorization of number

import sys
import math

def prime_factorize(n):
    """Returns the prime factors of n.
    Return value is a dictionary, key is a prime number which
    divides n and value is the power of that prime number in
    the prime factorization of n.

    E.g. prime_factorize(24) would return { 2: 3, 3:1 }
    as 24 = 2^3 * 3 ^1
    """

    def how_many_times_is_a_factor(n,m):
        """See if m divides n, and how many time
        Returns power p and newn where 
        n = newn * m^p
        If m does not divide n, returns p=0 and newn=n
        """
        newn = n
        p = 0

        while newn % m == 0:
            p = p + 1
            newn = int(newn / m)

        return p, newn


    results = {}

    # Handle special cases
    if n < 1:
        raise ValueError("n must be a positive integer")
    if n == 1:
        return { 1:1 }


    # If n has a factor, it must be less than max
    max = int(math.floor( math.sqrt(n) ) + 1)

    # Start with 2
    i = 2
    while i < max and n > 1:
        p, newn = how_many_times_is_a_factor(n, i)
        if p > 0:
            # Found a factor
            results[i] = p
            n = newn
            max = int(math.floor( math.sqrt(n) ) + 1)
        i = i + 1

    # Add n as factor if > 1
    if n > 1:
        results[n] = 1

    return results

def print_prime_factorization(n):
    """Print the prime factorization of n
    Uses prime_factorize function
    """

    results = prime_factorize(n)
    sys.stdout.write("Prime factorization of {}\n".format(n))
    sys.stdout.write("{}=\n".format(n))
    keys =sorted( results.keys() )
    for prime in keys:
        power = results[prime]
        sys.stdout.write("\t{}^{}\n".format(prime,power))
    return


if ( __name__ == '__main__' ):
    # Run the function if called as a script
    import argparse

    parser = argparse.ArgumentParser(
            prog='factorize',
            description='Prints the prime factorization of a number'
            )
    parser.add_argument('n')

    args = parser.parse_args()
    n = int(args.n)
    print_prime_factorization(n)