Criba de eratostenes

Solo disponible en BuenasTareas
  • Páginas : 2 (324 palabras )
  • Descarga(s) : 0
  • Publicado : 18 de enero de 2011
Leer documento completo
Vista previa del texto
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 terminacuando 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 losnú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 3031 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 393. 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 3537
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 2931 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 1317 19
23 29 31 37
Tabla de números primos
2 3 5 7 11 13 17 1923 29 31 37
41 43 47 53 59
61 67 71 73...
tracking img