1votos

Números primos hasta N en C

por josejuan hace 4 años

Sin ningún tipo de optimización, usando Eratóstenes, 23 segundos y 119 Mbytes de RAM.

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
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
 
//#define PRINT_PRIMES 
 
#define byte unsigned char 
 
int main(int argc, char **argv) { 
 
    int S = atoi(argv[1]) >> 3;                     // Size memory (bytes) 
    int N = S << 3;                                 // check hasta N (excluido) 
 
    byte *M = (byte *) malloc(sizeof(byte) * S);    // usaremos bits 
 
    memset(M, 0, S);                                // ponemos a 0 
 
    // desde 2 hasta N 
    int i = 2; 
    while(i < N) { 
 
        int ibyte = i >> 3;                         // ese nº está en el byte `ibyte` 
        int ibit  = 1 << (i & 7);                   // y ocupa el bit `i & 7` máscara en `ibit` 
 
        if((M[ibyte] & ibit) == 0) {                  // ¡éste es un nº primo! 
#ifdef PRINT_PRIMES 
            printf("%i\n", i); 
#endif 
            int j = i + i;                          // cada múltiplo de este primo... 
            while(j < N) { 
                M[j >> 3] |= 1 << (j & 7);          // ...lo ponemos como "no primo". 
                j += i; 
 
        i++; 
#ifndef PRINT_PRIMES 
        i--; 
        while(M[i >> 3] & (1 << (i & 7))) i--; 
        printf("%i\n", i); 
#endif 
 
    return 0; 
 
/* 
 
[josejuan@centella Solveet]$ cat /proc/cpuinfo | grep -i '\(model name\|mhz\)' | head -n 2 
model name      : AMD Phenom(tm) II X6 1045T Processor 
cpu MHz         : 2700.000 
 
[josejuan@centella Solveet]$ gcc -O3 primes.c 
[josejuan@centella Solveet]$ time -f "%E, %M" ./a.out 1000000000 
999999937 
0:23.10, 123292 
 
*/ 
1 comentario
1votos

Escrito por drabor hace 4 años

Usar índices en vez de los propios números y encima bits ya lo consideraría una gran optimización. Miedo me da el tiempo que pueda alcanzar cuando se limite a la raíz cuadrada :).

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.