0votos

Numeros Amigos de un Rango de numeros en C

por josejuan hace 5 años

Como la versión anterior pero usando ciclos de presumas y paralelizado (dos speedups comentados en la otra solución). Para los primeros 1.000.000.000 nº obtiene un speedup del 25% (3 minutos).

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
#include <stdio.h> 
#include <stdlib.h> 
 
int main(int argc, char **argv) { 
 
  int h = atoi(argv[1]), N = atoi(argv[2]); 
 
  { // cota superior múltiplo del doble de hilos 
    int r = N % h; 
    if(r != 0) N += h - r; 
 
  int z, i, S = N / h, *q = (int *) malloc(sizeof(int) * (N + 1)); 
 
  // del 1 al 12 hay un ciclo de tamaño 27720 (puede generalizarse haciendo "foldl lcm 1 [2..n]") 
 // mc = 12 -> sc = 27720 
#define MC 18 
#define SC 12252240 // foldl lcm 1 [2..MC] 
  int * r = (int *) malloc(sizeof(int) * SC); 
  for(z = 0; z < SC; z++) r[z] = 1; 
  for(z = 2; z <= MC; z++) for(i = z; i <= SC; i+=z) r[i - 1] += z; 
 
  // aplicamos todo (también paralelizable) 
  #pragma omp parallel for 
  for(z = 1; z <= N; z++) q[z] = r[(z - 1) % SC]; 
 
  #pragma omp parallel for 
  for(z = 1; z <= MC; z++) q[z] -= z; 
 
  // cada hilo actualiza su rango 
  #pragma omp parallel for 
  for(z = 0; z < h; z++) { 
    int i = 1, j = z * S + 1, k = j + S - 1, jm = j >> 1, km = k >> 1; 
    // si es menor que MC ya está hecho 
    if(i <= MC) i = MC + 1; 
    for(; i < jm; i++ ) { 
      int jr = j % i, u = j; 
      if(jr != 0) u += i - jr; 
      if(u == j) u += i; 
      while(u <= k) { q [u] += i; u += i; } 
    for(; i <= km; i++ ) { 
      int u = i + i; 
      while(u <= k) { q [u] += i; u += 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]); 
 
  return 0; 
 
 
 
/* 
 
[josejuan@centella amig]$ gcc  -O3 -fopenmp  a.c -o c 
[josejuan@centella amig]$ time -f "%E, %M" ./c 48 1000000000 > c.txt 
3:08.76, 3956076 
[josejuan@centella amig]$ tail c.txt  
902335744, 903709952 
903825416, 972264184 
907960904, 930631096 
912404025, 988724295 
914746450, 960133550 
916021964, 999258676 
917168950, 953023850 
930793204, 999728396 
948760928, 951278752 
957871508, 998051692 
[josejuan@centella amig]$  
 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.