import java.util.Scanner;

/* Dato un naturale n, produce la sua scomposizione in fattori primi,
 * stampando n = p1^e1 * p2^e2 * pk^ek
 * dove ciascun divisore compare con l'esponente opportuno (se diverso da 1)
 * Es.: 700 = 2^2 * 5^5 * 7
 * Questa versione limita l'esame ai divisori minori o uguali alla radice quadrata del
 * numero da fattorizzare
 */

public class FattorizzaConEsponenti
{
	public static void main(String[] args)
	{
		long numero;
		long radiceDiNumero;
		long residuoDaFattorizzare;
		long divisore;
		Scanner lettore = new Scanner(System.in);
		boolean primoFattore;
		
		System.out.print("Quale intero vuoi fattorizzare? ");
		numero = lettore.nextLong();
		
		radiceDiNumero = (long) Math.sqrt(numero);
		System.out.print(numero + " =");
		primoFattore = true;
		divisore = 2;
		residuoDaFattorizzare = numero;
		while(divisore <= radiceDiNumero)  // continua se la fattorizzazione non e' completa
		{
			int esponente = 0;
			while(residuoDaFattorizzare % divisore == 0)  // ciascun divisore potrebbe essere applicato piu' volte
			{
				esponente++;
				residuoDaFattorizzare = residuoDaFattorizzare / divisore;
			}

			if(esponente > 0)
			{
				// stampo il divisore
				if(primoFattore)     // in questo caso si tratta del primo fattore
				{
					System.out.print(" " + divisore);   // stampo senza il simbolo di moltiplicazione
					primoFattore = false;
				}
				else
				{
					System.out.print(" * " + divisore); // stampo premettendo il simbolo di moltiplicazione
				}
					
				// stampo l'eventuale esponente
				if(esponente > 1)
					System.out.print("^"+esponente);
			}				

			// ho esaurito l'applicazione del divisore
			divisore++;
		}
	 
		/*
		 * a questo punto abbiamo provato con tutti i divisori minori o uguali a sqrt(numero)
		 * ma il residuo potrebbe essere diverso da uno. Ad esempio, fattorizzando il numero 55
		 * l'esame dei divisori si arresta quando supero il valore 7, lasciando il residuo pari
		 * a 11 (poiche' abbiamo diviso per 5).
		 * In questo caso deve essere stampato l'ultimo fattore, che e' proprio pari al residuo
		 */
		if(residuoDaFattorizzare > 1)
		{
			if(primoFattore) // si potrebbe anche trattare del primo fattore
				System.out.print(" " + residuoDaFattorizzare);
			else
				System.out.print(" * " + residuoDaFattorizzare);
		}
		System.out.println();
	}
}