#!/usr/bin/python

def make_offsets(primes):
    '''
    `primes` MUST be a list of all primes from 2 to stop.
    
    All primes except 2 and 3 are 6n - 1 or 6n + 1 because
    2*3 = 6 (the period) and 6n+1 and 6n-1 are the only possible
    primes when n > 0.
    
    This function extends this beyond just 2, 3, 6n+1 and 6n+5.
        
    Returns: period, offsets
    
    Notice: `offsets` will include 1 and will not include any prime
    in `primes`.  Exceptions need to be made when n == 0.
    
    Example
    =======
    
        >>> period, offsets = table(2, 3, 5)
        >>> period
        30
        >>> offsets
        [1, 7, 11, 13, 17, 19, 23, 29]
    '''
    # Calculate the period.
    period = 1
    for p in primes:
        period *= p
    # Calculate valid offsets
    offsets = []
    i = 0
    while i < period:
        if all(map(lambda x: i%x, primes)):
            offsets.append(i)
        i += 1
    # Done.
    return period, offsets


def factorise(num):
    '''
    Return a list of (prime, power).
    '''
    # Handle bad values of `num`.    
    factors = []
    if num != int(num):
        raise TypeError('`num` MUST be an integer.')    
    elif num < -1:
        factors.append((-1, 1))
        num = -num
    elif num == -1:
        return [(-1, 1)]
    elif num == 0:
        return [(0, 1)]
    elif num == 1:
        return [(1, 1)]
    
    # There is no need to only use primes here.
    # Consider this example: 2, 3, 4, 5
    # There will be no 4s because the 2s have already been
    # divided away.
    # 
    # Checking whether or not the number is a prime will take
    # a longer time than realising it won't divide `num`, so
    # why bother?
    # 
    # The "only" thing that could make this faster is to not use
    # so damn many composite numbers in the first place, that's
    # where the `make_offsets` function comes to use.
    #
    # Use the `make_offsets` function to exclude some composite numbers.
    # Primes are {2, 3, 5} when n == 0 and {6n+1, 6n+5} when n > 0
    # Extend this beyond just 2*3, go to 2*3*5*7*11*13*17
    # 
    #global primes      # Won't be modified, global declarations only
    #global period      # here for clarity.
    #global offsets
    
    table = primes + offsets[1:]    # Offset table to use when n == 0.
    
    n_times_period = 0      # n alone is only needed for checking if n is
                            # zero or not.
    
    sqrt_num = num**0.5     # If the potential divident > sqrt(num) then
                            # there must have been a previous divident, but
                            # there wasn't. Therefore`, `num` must be prime.
    
    # Can't handle num == 1 properly.
    while num > 1:
        for offset in table:
            divident = n_times_period + offset
            # Check if `num` is prime.
            if divident > sqrt_num:
                factors.append((num, 1))
                num = 1
                break
            # Divide away the selected factor.
            power = 0
            while num % divident == 0:
                power += 1
                num /= divident
            if power:
                factors.append((divident, power))
                # `num` does not magically become 1 -> continue in same block.
                if num == 1:
                    break
                # `num` has changed, change `sqrt_num`
                sqrt_num = num**0.5
        # Offset table to use when n > 0.
        # Change only once.
        if n_times_period == 0:
            table = offsets
        # Next iteration:
        n_times_period += period
    
    return factors


def main():
    import sys
    try:
        while True:
            # Get input
            sys.stderr.write('\nEnter number to factorise: ')
            sys.stderr.flush()
            line = sys.stdin.readline()
            if not line:
                break
            if line == '\n':
                # Shut up.
                continue
            # Parse input
            try:
                num = int(line)
            except ValueError as e:
                sys.stderr.write(str(e) + '\n')
                continue
            # Compute input
            try:
                factors = factorise(num)
            except ValueError as e:
                sys.stderr.write(str(e) + '\n')
                continue
            # Print out.
            s = ' * '.join(map(lambda x: '{}**{}'.format(*x), factors))
            sys.stdout.write('{} = {}\n'.format(num, s))
    except KeyboardInterrupt:
        pass
    sys.stderr.write('\n')


# Pre-initialize the offsets table.

primes = [2, 3, 5, 7, 11, 13, 17]   # Becomes slow at 19.
period, offsets = make_offsets(primes)


if __name__ == '__main__':
    main()