Criba de Eratóstenes

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.
-Se parte de una lista, la cual va de 2 hasta elnúmero dado.
-Se elimina de la lista los múltiplos de 2.
-Luego tomamos el primero número después del 2 que no fue eliminado, en este caso el 3, y eliminamos de la lista los múltiplos de dicho número,así sucesivamente con los demás números.
-El proceso finaliza cuando el cuadrado del mayor número confirmado como primo es menos que el número final de la lista.
* Todos los números que permanecen enla lista son los números primos comprendidos de 2 al número dado.
Ejemplo:
Vamos a calcular por este algoritmo los números primos menores que 40.
1. Escribimos los números, en nuestro caso seránlos 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. Eliminamoslos 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. Elsiguiente 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 quedanson primos.
    
2
3
   
5
   
7
   
   
   
11
   
13
   
   
   
17
   
19
   
   
   
23
   
   
   
   
   
29
   
31
   
   
   
   
   
37
   
   
   ...