primes2.py

import math

def prime_factorization(n):
    factors = []
    
    count = 0
    while n % 2 == 0:
        n //= 2
        count += 1
    if count > 0:
        factors.append((2, count))
    
    f = 3
    while f * f <= n:
        count = 0
        while n % f == 0:
            n //= f
            count += 1
        if count > 0:
            factors.append((f, count))
        f += 2
    
    if n > 1:
        factors.append((n, 1))
    
    return factors


if __name__ == "__main__":
    N = int(input().strip())
    factors = prime_factorization(N)
    result_parts = []
    
    for prime, power in factors:
        if power == 1:
            result_parts.append(f"{prime}")
        else:
            result_parts.append(f"{prime}^{power}")
    
    print(" * ".join(result_parts))