Descomposición en primos P42051
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
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
- Author
- Omer Giménez
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++