'''
Factoring an input integer. For example: 64 yields 2^(6), 48 yields: 2^(4)x3
and 921 yields 307x3. All the factos are primes. If the input is prime
it is detected as well.
'''
import math
def main():
    num=int(input('enter anumber to be factored: '))
    sq=math.sqrt(num)
    sq=int(sq)
    '''
    make prime array
    Generate all primes up to the square root of the
    number to be factored
    '''
    prime_arr=primes_gen(sq)
    num_left=num
    result_arr=[]
    while num_left> 1: #divide until 1, or getting a prime
        pi=0
        # while loop to find a divider
        while  pi<len(prime_arr) and num_left%prime_arr[pi]!=0 :
            pi+=1
            last_num=num_left
        if pi<len(prime_arr): # found a divider
            result_arr.append(prime_arr[pi])
            num_left //=prime_arr[pi]
            last_num=num_left
        else:
            num_left=0
    if len(result_arr)> 0 and last_num!=1:
        result_arr.append(last_num)
    elif last_num==num:
        print(num, ' is prime')
    if num_left != num and last_num != num:
        #Build the multiplication string
        mult_str=''
        for i in range(len(result_arr)):
            mult_str+=str(result_arr[i])+'x'
        print(improve_powers(mult_str[0:-1]))
#----------------------------------------------------------------------------
def improve_powers(st1): #Make the result nicer with powers etc.
    #Gets as a parm, a string like: n1xn2xn3x..... (n1, n2, n3 all primes)
    final_result=''
    factors=st1.split('x')
    factors=list(map(int,factors)) #turn the array of strings to arr of ints
    d={}                           #Keep num and its power, i.e. {2:3,5:1,..}
    power=0
    new_base=0
    for num in factors:
        if num==new_base:
            power+=1
        else:
            if new_base !=0:
                d[new_base]=power
            new_base=num
            power=1
    d[new_base]=power #last array factor
    result=''
    for key in d: #Format for example: {2:3,5:2,7:1} to 2^(3)x5^(2)x7
        if d[key] >1:
            result+=str(key)+'^('+str(d[key])+')x'
        else:
            result +=str(key)+'x'
    result=result[:-1]
    return result
#----------------------------------------------------------------------------
def primes_gen(limit): #Generates primes up to 'limit'
    #Receives an integer parm, returns a list of primes up to that parm
    prime_cand=2
    prime_arr=[]
    while prime_cand <= limit:
        if prime_check(prime_cand):
            prime_arr.append(prime_cand)
        prime_cand +=1
    return prime_arr
#----------------------------------------------------------------------------
def prime_check(cand): #Check if an integer is prime
    div=2
    if cand==2:
        return 1
    upper_div=int(math.sqrt(cand))
    while div <= upper_div:
        if cand//div == cand/div:
            return 0
        else:
            div +=1
    return 1
#----------------------------------------------------------------------------
if __name__ == '__main__':
    main()