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
...
Regístrate para leer el documento completo.