Factorizar el factorial

propuesto por josejuan

Obtener la descomposición en factores primos (con sus exponentes, claro) del factorial de un número natural dado.

Enunciado
Por ejemplo, la descomposición en factores primos de 90! es
2^86 * 3^44 * 5^21 * 7^13 * 11^8 * 13^6 * 17^5 * 19^4 * 23^3 * 29^3 * 31^2 *
37^2 * 41^2 * 43^2 * 47^1 * 53^1 * 59^1 * 61^1 * 67^1 * 71^1 * 73^1 * 79^1 *
83^1 * 89^1


La de 500! es
2^494 * 3^247 * 5^124 * 7^82 * 11^49 * 13^40 * 17^30 * 19^27 * 23^21 *
29^17 * 31^16 * 37^13 * 41^12 * 43^11 * 47^10 * 53^9 * 59^8 * 61^8 *
67^7 * 71^7 * 73^6 * 79^6 * 83^6 * 89^5 * 97^5 * 101^4 * 103^4 * 107^4 *
109^4 * 113^4 * 127^3 * 131^3 * 137^3 * 139^3 * 149^3 * 151^3 * 157^3 *
163^3 * 167^2 * 173^2 * 179^2 * 181^2 * 191^2 * 193^2 * 197^2 * 199^2 *
211^2 * 223^2 * 227^2 * 229^2 * 233^2 * 239^2 * 241^2 * 251^1 * 257^1 *
263^1 * 269^1 * 271^1 * 277^1 * 281^1 * 283^1 * 293^1 * 307^1 * 311^1 *
313^1 * 317^1 * 331^1 * 337^1 * 347^1 * 349^1 * 353^1 * 359^1 * 367^1 *
373^1 * 379^1 * 383^1 * 389^1 * 397^1 * 401^1 * 409^1 * 419^1 * 421^1 *
431^1 * 433^1 * 439^1 * 443^1 * 449^1 * 457^1 * 461^1 * 463^1 * 467^1 *
479^1 * 487^1 * 491^1 * 499^1


El problema lo he tomado de Programming Praxis

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

6 Soluciones

Dar mi solución

0votos
Factorizar el factorial en Java
por

PinaGamer

hace 5 años

Simple y sencillo para todos los amigos del 0 y del 1. Usando dos métodos auxiliares al main. Uno calcula el factorial del entero creado en el main y a su vez, llama al método factor que directamente descompone el factorial.

0votos
Factorizar el factorial en Haskell
por

josejuan

hace 5 años

Esta solución es de Will Ness y es sencillamente genial. Con la implementación eficiente de Data.Numbers.Primes tiene un rendimiento similar a la versión de C, pero además, si se cachean los primos (o leen de disco) sería inmediato.

Dar mi solución