1votos

Factorizar el factorial en C

por josejuan hace 5 años

Coste O(n/2 log log n) y espacio O(n) usando una criba. No se requiere ni precálculo de números primos, ni divisiones, ni multiplicaciones, ... sólo sumas.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/* 
 
  El coste del algoritmo (salvo error, claro) es 
 
    O(n/2 * log log n) 
 
  (lo de dividir por 2 es por destacar la reducción 
  a la mitad del bucle principal). 
 
  Únicamente usa sumas (ni raíces, ni precalcular los 
  números primos, ni divisiones, ni módulos, etc...). 
 
  Creo que "en las distancias cortas" éste es mejor 
  algoritmo que el que ponen en Programming Praxis, 
  aunque usando la criba de Atkin me parece que el 
  de Will Ness tiene mejor complejidad asintótica. 
 
  La estrategia consiste en hacer una criba de arriba (n/2) 
  a abajo (2) de la mitad de los números, de ellos, volvemos 
  a subir multiplicando (2, 3, ...) para ir obteniendo las 
  veces que es multiplicado. 
 
  En mi AMD Phenom(tm) II X6 a 2,7GHz le toma como 1 segundo 
  calcular la factorización del factorial 
 
      10000000!    (alrededor de 10e67500000) 
 
 
  La relación usada es la siguiente: 
 
    Si un número `z` tiene dos factores (no necesariamente primos) 
 
        z = a * b 
 
    entonces, las potencias que posea `z` pueden ser "trasladadas" 
    simultáneamente a `a` y a `b`. 
 
    Por ejemplo, si un factor aparece `k` veces 
 
       z^k 
 
    y es 
 
      z = a * b 
 
    es 
 
      z^k = (a * b)^k = a^k * b^k 
 
*/ 
 
#include <stdio.h> 
#include <stdlib.h> 
 
int main(int argc, char **argv) { 
  int n = atoi(argv[1]); 
  int *p = (int *) malloc(sizeof(int) * (n + 1)); 
  int i, j, d; 
  for(i = 0; i <= n; i++) 
    p[i] = 1; 
  for(i = n >> 1; i > 1; i--) 
    if(p[i]) { 
      for(j = i + i, d = 2; j <= n; j += i, d++) { 
        if(p[j]) { 
          p[i] += p[j]; 
          p[d] += p[j]; 
          p[j] = 0; 
  printf("Factors ["); // imprimo la salida como en Haskell para validar con `diff` 
  for(i = 2; i <= n; i++) 
    if(p[i]) 
      printf("%s%i,%i)", i==2?"(":",(", i, p[i]); 
  printf("]\n"); 
  return 0; 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.