Solución a la Tarea 3: Factorizando Factoriales

A continuación muestro un programa que resuelve el problema propuesto. Observe que todo el trabajo se hace en las funciones primo (que regresa cero en cuanto encuentra un divisor de p) y factor (que calcula la suma n/p + n/p² + n/p³ + ...). Lo único que hace la función main es llamar a factor si ya ha determinado que un número es primo. Observe también que el programa no calcula el valor de n! pues no cabría en una variable entera incluso para valores muy pequeños de n (9! = 362,880 > 65,536 = 2¹⁶, 13! = 6,227,020,800 > 4,294,967,296 = 2³² y 21! = 51,090,942,171,709,440,000 > 18,446,744,073,709,551,616 = 2⁶⁴).

#include <stdio.h>

int primo(long int p)
{
long int i;

for (i = 2; i*i <= p; i++)
    if (p%i == 0)
      return 0;
return 1;
}

long int factor(long int n, long int p)
{
long int f = 0;

do {
    n = n/p;
    f += n;
} while (n >= p);
return f;
}

int main(void)
{
long int n, p;

scanf("%ld", &n);
for (p = 2; p <= n; p++)
    if (primo(p))
      printf("%ld^%ld ", p, factor(n, p));
printf("\n");
return 1;
}

Los valores de entrada y salida empleados para la evaluación fueron los siguientes:

Entrada Salida
      2 2^1
      3 2^1 3^1
      4 2^3 3^1
      5 2^3 3^1 5^1
      6 2^4 3^2 5^1
     10 2^8 3^4 5^2 7^1
     11 2^8 3^4 5^2 7^1 11^1
     12 2^10 3^5 5^2 7^1 11^1
     13 2^10 3^5 5^2 7^1 11^1 13^1
     14 2^11 3^5 5^2 7^2 11^1 13^1
     15 2^11 3^6 5^3 7^2 11^1 13^1
     20 2^18 3^8 5^4 7^2 11^1 13^1 17^1 19^1
     30 2^26 3^14 5^7 7^4 11^2 13^2 17^1 19^1 23^1 29^1
     40 2^38 3^18 5^9 7^5 11^3 13^3 17^2 19^2 23^1 29^1 31^1 37^1
     50 2^47 3^22 5^12 7^8 11^4 13^3 17^2 19^2 23^2 29^1 31^1 37^1 41^1 43^1 47^1