1014. Product of Digits

Your task is to find the minimal positive integer number Q so that the product of digits of Q is exactly equal to N.

Input
The input contains the single integer number N (0 ≤ N ≤ 109). 

Output
Your program should print to the output the only number Q. If such a number does not exist print −1.

Sample
Input
10

Ouput 
25 

http://acm.timus.ru/problem.aspx?space=1&num=1014 

La solucion consiste en descomponer el numero N en todos los factores posibles
que sean menores o igual que 9. 

Luego acomodar estos factores obtenidos de tal manera que el numero formado 
sea el menor posible. 

Para lograr eso podemos ir diviendo buscando sus divisores
de mayor a menor, es decir comenzando con el 9 e ir disminuyendo hasta el 8, cada
divisor que encontremos lo añadimos de izquierda a derecha en la salida, de tal
manera que los divisores mas pequeños aparezcan a la izquierda y los mas grandes
aparezcan a la derecha, lo cual haria que el valor del numero formado sea minimo.

Ejm:   N = 588 = 84 * 7 = 12 * 7 * 7 = 2 * 6 * 7 * 7

       -> Numero Buscado = 2677
    
Obs: Si el numero tiene un factor primo mayor que 9, entonces no existiria solucion,
ya que un numero >= 10 no se podria representar como un solo digito en la solucion.

public class Problema1014 
{
   public static void main( String[] args ) throws Exception
   {
      int numero = sig();
  
      System.out.println( buscar( numero ) );
   }
 
   public static String buscar( int numero )
   {  
      // Verificamos los casos especiales
      if( numero == 0 )
         return "10";
  
      if( numero == 1 )
         return "1";
  
      String salida = "";

      // Buscamos  de mayor a menor los divisores menores que 10
      // y los vamos añadiendo a la salida de manera adecuada para
      // que al final los digitos menores esten en el extremo 
      // izquierdo y los digitos mayores en el extremo derecho.
      for( int i = 9; i > 1; i -- )
      {
         while( numero % i == 0 )
         {
            salida = i + salida;
            numero = numero / i;
         }
      }
  
      // El numero tiene un factor primo mayor que 9
      if( numero > 1 )
         return "-1";
  
      else
         return salida;
   }
 
   public static int sig() throws Exception
   {
      int val = System.in.read() - 48;
      int car = System.in.read();
  
      while( car > 47 && car < 58 )
      {
         val = 10 * val + car - 48;
         car = System.in.read();
      }
  
      return val;
   }
}