0votos

numeros amigos en C

por josejuan hace 5 años

Aunque el desafío es chequear dos amigos, uno relacionado es obtener todos los posibles. Una forma sencilla similar a la criba de Eratóstenes nos permite obtener en pocos minutos todos los amigos hasta el número 1.000.000.000

Escribir una función que determine si dos números dados son 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
/* 
 
    AQUÍ NO SE RESUELVE EL DESAFÍO. 
 
    Se resuelve una variante, que es encontrar todos 
    los números amigos hasta un `n` dado (donde ese 
    `n` es límite del mayor del par de amigos). 
 
    La estrategia es muy parecida a la criba de 
    Eratóstenes, solo que lo hacemos para cada N. 
 
    Mantenemos el contador para cada 1..N. 
 
    El proceso es fácilmente paralelizable. 
 
    El proceso admite estrategias de optimización 
    (no implementadas) como los ciclos módulo similares 
    a las cribas para números primos. 
 
    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. 
 
    De forma adicional, el proceso se puede paralelizar 
    también fácilmente, bien porque se pueden dividir 
    los intervalos (más fácil pero peor paralelización), 
    bien porque se pueden revisar los divisores de forma 
    independiente (más difícil por tema de bloqueos pero 
    mejor paralelización). 
 
*/ 
 
#include <stdio.h> 
#include <stdlib.h> 
 
void main(int argc, char **argv) { 
    int i, j, N = atoi(argv[1]), *q = (int *) malloc(sizeof(int) * (N + 1)); 
    for(i = 1; i <= N; i++) q[i] = 1; 
    for(i = 2; i <= N; i++) for(j = i + i; j <= N; j += i) q[j] += i; 
    for(i = 1; i <= N; i++) if(q[i] > i && q[i] <= N && q[q[i]] == i) printf("%i, %i\n", i, q[i]); 
 
/* 
 
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 
 
*/ 
5 comentarios
0votos

Escrito por Jabar hace 5 años

hola josejuan cuanto tiempo le toma a tu programa calcular hasta el 998051692
0votos

Escrito por josejuan hace 5 años

¬¬ lo pone en la solución :D :D 4 minutos 34 segundos consumiendo 4 Gbytes de RAM.
0votos

Escrito por josejuan hace 5 años

Pero OJO ten en cuenta que se están obteniendo TODAS las parejas, por ejemplo, usando mi algoritmo anterior (en Haskell) para verificar si dos números son amigos, le toma:

$ ./checkAmigos 957871508 998051692
Amigos: True
tiempo: 2.675056457519531e-4


Pero sólo está mirando dos números concretos.
0votos

Escrito por ilopez hace 5 años

Ahora explica la lógica que sigues de manera mas simple y entendible para el resto de los mortales.
0votos

Escrito por josejuan hace 5 años

Perdón, me pareció evidente, por eso sólo apunté el tema de la complejidad.

La pondré como solución ya que han puesto un desafío específico.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.