Descomposición en primos P42051


Statement
 

pdf   zip

thehtml

Hay pocas cosas más fastidiosas que cuando en clase de matemáticas te piden que descompongas un número en sus factores primos. Empiezas a dividir por 2, por 3, por 5, etc., sabiendo que estás a la merced de que el profesor haya tenido la delicadeza de escoger un número que descomponga en primos pequeños y no, pongamos, un número de 9 cifras cualquiera al azar.

Te pedimos que rompas esta dependencia en la buena voluntad de tu profesor de matemáticas y que escribas un programa que sea capaz de descomponer miles de números cualesquiera de hasta 9 cifras en menos de 1 segundo.

Entrada

La entrada consiste en un número 1≤ n≤ 5000 seguido de n líneas, cada una con un número k entre 2 y 999999999.

Salida

Escribe n líneas con la descomposición en primos de los n números, siguiendo el formato de los ejemplos (primos de menor a mayor, elevados a la potencia que corresponda excepto en el caso de que sea ‍1).

Puntuación

  • TestA:  ‍55 Puntos ‍

    Entradas donde los n números son números “escogidos” por el profesor, donde todos los factores primos estan entre 2 y 97, como el Ejemplo ‍1.

  • TestB:  ‍ Entradas de todo tipo, como el Ejemplo ‍2.  ‍45 Puntos ‍
Public test cases
  • Input

    10
    835430400
    281410920
    141702912
    294769800
    64067328
    217131408
    15253029
    729855360
    94379810
    24883240
    

    Output

    835430400=2^11*3^2*5^2*7^2*37
    281410920=2^3*3^2*5*7^3*43*53
    141702912=2^8*3^3*13*19*83
    294769800=2^3*3^3*5^2*13^2*17*19
    64067328=2^8*3^3*13*23*31
    217131408=2^4*3^3*13*23*41^2
    15253029=3^4*11*17*19*53
    729855360=2^7*3^5*5*13*19^2
    94379810=2*5*7*23*31^2*61
    24883240=2^3*5*17*23*37*43
    
  • Input

    10
    20025635
    768136121
    688078471
    1125624
    332808255
    615185077
    511375961
    182213845
    821857325
    960487559
    

    Output

    20025635=5*7*572161
    768136121=137*5606833
    688078471=1291*532981
    1125624=2^3*3*46901
    332808255=3^2*5*13*568903
    615185077=13*47321929
    511375961=1049*487489
    182213845=5*11*331*10009
    821857325=5^2*1669*19697
    960487559=21803*44053
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++