[zerojudge] e929: pC. 分解質因數

import sys 
import math

limit = 20000000
u = int(math.sqrt(limit))
sieve = [0, 0, 2, 3] + [1] * (u - 4)
prime = [2]
for i in range(3, u, 2):
    if(sieve[i] == 0): continue
    prime.append(i)
    for j in range(i * i, u, i): 
        sieve[j] = 0

def fact(n):
    r = []
    k = math.sqrt(n)
    for x in prime:
        if(x > k): break
        if(x > n): break 
        c = 0
        while(n % x == 0):
            c += 1
            n //= x
        if(c): r.append([x,c])
    if(n > 1): r.append([n,1])
    return r

def op(z):
    if(z[1] == 1): return str(z[0])
    return '{}^{}'.format(*z)
    
for s in sys.stdin:
    n = int(s)
    f = fact(n)
    r = list(map(op, f))
    print('{} = {}'.format(n, ' * '.join(r)))