# Arup Guha
# 10/25/2018
# Prime Factorization for Fall 2018 CIS 3362 Q1

# Just prints out the prime factorization of n and phi of n.
def primefact(n):

    i=2
    phi = n
    while i*i <= n:
        exp = 0
        while n%i == 0:
            n //= i
            exp+=1
        if exp > 0:
            print(i,"^",exp," * ",sep="",end="")
            phi = phi - phi//i
        i += 1

    if n > 1:
        print(n,"^1", sep="")
        phi = phi - phi//n

    print("phi(",n,") = ", phi, sep="")

primefact(6019208928)