1votos

Numeros Amigos de un Rango de numeros en C

por josejuan hace 5 años

Todos los amigos entre 1 y N. Sólo se usan sumas (de hecho incrementos).

Dado un rango de numeros (Ejem. 1 10000) arrojar en pantalla los pares de numeros amigos.

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>  
#include <stdlib.h>  
void main(int argc, char **argv) {  
    int i, j, N = atoi(argv[1]); 
/*  
 
    Se pueden obtener todos los amigos entre 
     
            1 .. N 
     
    donde N es el mayor de los mayores amigos 
    (dados dos amigos, uno de los dos es mayor). 
  
    Además, sólo realizando sumas. 
     
    Lo que hacemos es tener un contador para cada 
    uno de esos 1 .. N números 
*/ 
    int *q = (int *) malloc(sizeof(int) * (N + 1));  
     
/*     
    como el 1 divide a todos, inicializamos ese 
    contador, para todos, a 1. 
*/ 
    for(i = 1; i <= N; i++) q[i] = 1; 
     
/* 
    Ahora, para cada posible divisor, 2, 3, 4, 5, ... 
    hacemos como en las cribas, es decir, vamos "saltando" 
    de 2 en 2, de 3 en 3, de 4 en 4, de 5 en 5, ... y, 
    como esos son precisamente los múltiplos, le añadimos 
    nuestro divisor. 
*/ 
    for(i = 2; i <= N; i++) for(j = i + i; j <= N; j += i) q[j] += i;  
 
/* 
    Así tendremos en cada contador, la suma de todos los 
    divisores del número al que corresponde dicho contador. 
     
    Por tanto, dado un índice `n`, el número en su contador será 
    su amigo si el contador del contador ha sumado `n`. 
*/ 
    for(i = 1; i <= N; i++) if(q[i] > i && q[i] <= N && q[q[i]] == i) printf("%i, %i\n", i, q[i]);  
/* 
    Y ya está. 
*/ 
  
/* 
    El proceso es fácilmente paralelizable, porque se pueden 
    sumar en paralelo para cada `i` sus `N/i` valores y, además, 
    sincronizando los contadores, pueden paralelizarse todas las 
    rondas de `2..N`. 
 
    También puede hacerse optimizaciones al algoritmo como los 
    ciclos módulo similares a las cribas para números primos. Por ejemplo, 
    se pueden combinar las sumas de 2, 4 y 8, sabiendo que éstas van como 
 
      Para el 2: 2 0 2 0 2 0  2 0 2 0 2 0 2 0  2 0 2 0 ... 
      Para el 4: 0 0 4 0 0 0  4 0 0 0 4 0 0 0  4 0 0 0 ... 
      Para el 8: 0 0 0 0 0 0  8 0 0 0 0 0 0 0  8 0 0 0 ... 
    --------------------------------------------------------- 
      Suma ciclo 2 0 6 0 2 0 14 0 2 0 6 0 2 0 14 0 2 0 ... 
 
    Entonces, hemos reducido la suma incremental a una iteración en lugar 
    de 3. 
 
    Por otro lado, el coste total del proceso es "casi" O(n) porque 
    para cada i se revisan (n-i)/i elementos  
  
       n + (n - 2) / 2 + (n - 3) / 3 + ...  
  
    es decir  
  
  
        n (1/2 + 1/3 + ... + 1/n)  
  
    El armónico no tiene expresión general y de hecho  
    diverge, pero taaaaaaaaan lentamente que hacen  
    falta entradas muy grandes para separarse de la lineal.  
  
*/  
  
/*  
  
Un ejemplo de ejecución:  
  
[josejuan@centella solveet]$ time -f "%E, %M" ./amigos1 1000000000 > amigos.txt  
Command exited with non-zero status 162  
4:34.05, 3906736  
  
[josejuan@centella solveet]$ head amigos.txt  
220, 284  
1184, 1210  
2620, 2924  
5020, 5564  
6232, 6368  
10744, 10856  
12285, 14595  
17296, 18416  
63020, 76084  
66928, 66992  
  
[josejuan@centella solveet]$ tail amigos.txt  
902335744, 903709952  
903825416, 972264184  
907960904, 930631096  
912404025, 988724295  
914746450, 960133550  
916021964, 999258676  
917168950, 953023850  
930793204, 999728396  
948760928, 951278752  
957871508, 998051692  
  
[josejuan@centella solveet]$ wc -l amigos.txt  
564 amigos.txt  
  
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.