---

import java.util.*;

 

public class a010

{

public static int AddValue(int value) //用來增加HashMap中的次數

{

return value+1;

}

public static void main(String[] args)

{

boolean prime;

HashMap<Integer,Integer> primefactor=new HashMap<Integer,Integer>(); //HashMap用法不懂的可以上網查 這次用在"每個因數=出現次數"

 

Scanner sc=new Scanner(System.in);

int number=sc.nextInt();

 

while(number%2==0) //先把2這個質數的因數次數算出來

{

if(primefactor.containsKey(2)) //如果primefactor包含2 就把2的次數+1

primefactor.put(2,AddValue(primefactor.get(2)));

else //如果沒有包含2 則把2放進去(此時次數為1)

primefactor.put(2,1);

number/=2; //每次找到一個因數 number就要/該因數

}

for(int i=3;i<=number;i+=2) //偶數一定不是質數 因此直接從3開始 並且+2跑下去

{

prime=true;

for(int j=3;j<=Math.sqrt(i);j+=2) //根據數學公式 只要跑到根號i即可判斷出是否為質數

if(i%j==0) //發生整除 -> 不是質數

{

prime=false;

break;

}

if(prime)

while(number%i==0) //如果是質數 就一直算出該質因數的次數

{

if(primefactor.containsKey(i)) //如果primefactor包含2 就把2的次數+1

primefactor.put(i,AddValue(primefactor.get(i)));

else //如果沒有包含i 則把i放進去(此時次數為1)

primefactor.put(i,1);

number/=i;

}

if(number==1) //number=1的時候代表質因數都找完了 可以直接退出迴圈

break;

}

 

ArrayList<Integer>sort_map=new ArrayList<Integer>(primefactor.keySet()); //對HashMap做排序

Collections.sort(sort_map);

 

for(int i=0;i<sort_map.size()-1;i++) //輸出質因數

{

if(primefactor.get(sort_map.get(i))==1)

System.out.print(sort_map.get(i)+" * ");

else

System.out.print(sort_map.get(i)+"^"+primefactor.get(sort_map.get(i))+" * ");

}

if(primefactor.get(sort_map.get(sort_map.size()-1))==1) //輸出最後一個質因數 後面不能有'*' 所以做額外處理

System.out.print(sort_map.get(sort_map.size()-1));

else

System.out.print(sort_map.get(sort_map.size()-1)+"^"+primefactor.get(sort_map.get(sort_map.size()-1)));

 

sc.close();

}

}