0votos

Números primos hasta N en C

por josejuan hace 4 años

Haciendo un poco el bruto y añadiendo la cota anotada por @drabor rebajamos a 5,3 segundos (caben aún muchas optimizaciones como usar máscaras para los primeros primos, por ejemplo para 2, 3, 5 y 7 puede crearse un ciclo de 105 máscaras para inicializar; otra pequeña es ver si todos los bits están a 1 y saltar el tamaño de la palabra; ...).

Obtener todos los números primos menores o iguales a N en el menor tiempo posible.

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
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <omp.h> 
#include <windows.h> 
 
#define WORD unsigned char 
#define BITS 8 
#define POW 3 
 
int main(int argc, char **argv) { 
    LARGE_INTEGER frequency; 
    LARGE_INTEGER t1, t2; 
    double elapsedTime; 
    QueryPerformanceFrequency(&frequency); 
    QueryPerformanceCounter(&t1); 
 
    int n = 1000; 
    if (argc > 1) 
        n = atoi(argv[1]); 
 
    int S = n >> POW; 
    int N = S << POW; 
    int T = (int) (sqrt(N) + 1); 
 
    WORD *M = (WORD *) malloc(sizeof(WORD) * S); 
    memset(M, 0, S); 
 
#pragma omp parallel 
        int th  = omp_get_thread_num(); 
        int nth = omp_get_num_threads(); 
        printf("Thread %i / %i\n", th, nth); 
        WORD *W = M; 
        int i; 
        for (i = 2 + th; i < T; i += nth) { 
            int ibyte = i >> POW; 
            int ibit = 1 << (i & (BITS - 1)); 
            if ((W[ibyte] & ibit) == 0) { 
                int j; 
                for (j = i + i; j < N; j += i) 
                    W[j >> POW] |= 1 << (j & (BITS - 1)); // atómica? 
 
        int z, i = N; 
        for (z = 0; z < 15; z++) { 
            i--; 
            while (M[i >> POW] & (1 << (i & (BITS - 1)))) i--; 
            printf("%i\n", i); 
 
    QueryPerformanceCounter(&t2); 
    elapsedTime = (t2.QuadPart - t1.QuadPart) * 1.0 / frequency.QuadPart; 
    printf("%f seconds\n", elapsedTime); 
    return 0; 
/* 
 
// Intel® Xeon® Processor E3-1230 (8M Cache, 3.20 GHz) 
 
C:\>set OMP_NUM_THREADS=16 
C:\>eratostenes.exe 1000000000 
Thread 0 / 16 
Thread 4 / 16 
Thread 10 / 16 
Thread 9 / 16 
Thread 13 / 16 
Thread 1 / 16 
Thread 5 / 16 
Thread 7 / 16 
Thread 8 / 16 
Thread 3 / 16 
Thread 2 / 16 
Thread 11 / 16 
Thread 12 / 16 
Thread 6 / 16 
Thread 14 / 16 
Thread 15 / 16 
999999937 
999999929 
999999893 
999999883 
999999797 
999999761 
999999757 
999999751 
999999739 
999999733 
999999677 
999999667 
999999613 
999999607 
999999599 
5.292874 seconds 
 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.