Criba de Eratóstenes

La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado.

Partimos de una lista de números que van de 2 hasta un determinado número.

Eliminamos de la lista los múltiplos de 2.

Luego tomamos el primer número después del 2 que no fue eliminado (el 3) y eliminamos de la lista sus múltiplos, y así sucesivamente.

El proceso termina cuando el cuadrado del mayor número confirmado como primo es menor que el número final de la lista.

Los números que permanecen en la lista son los primos.

Vamos a calcular por este algoritmo los números primos menores que 40.

1. Escribimos los números, en nuestro caso serán los comprendidos entre 2 y 40.

     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

2. Eliminamos los múltiplos de 2.

2 3     5   7     9     11     13     15     17     19    
21     23     25     27     29     31     33     35     37     39    

3. El siguiente número es 3, como 32 < 40 eliminamos los múltiplos de 3.

     2 3     5     7             11     13             17     19    
        23     25             29     31             35     37            

4. El siguiente número es 5, como 52 < 40 eliminamos los múltiplos de 5.

     2 3     5     7             11     13             17     19    
        23                     29     31                     37            

 

5. El siguiente número es 7, como 72 > 40 el algoritmo termina y los números que nos quedan son primos.

     2 3     5     7             11     13             17     19    
        23                     29     31                     37            

Tabla de números primos

     2 3     5     7             11     13             17     19    
        23                     29     31                     37            
41     43             47                     53                     59    
61                   67             71     73                     79    
        83                     89                             97            
                                                                               
101     103             107     109             113                            
                        127             131                     137     139    
                                149     151                     157            
    163                 167                     173                     179    
181                                     191     193             197     199