La Criba De Eratóstenes
Páginas: 3 (593 palabras)
Publicado: 2 de agosto de 2012
LA 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 N. Se forma una tabla con todos los números naturalescomprendidos entre 2 y N y se van tachando los números que no son primos de la siguiente manera: cuando se encuentra un número entero que no ha sido tachado, ese número es declarado primo, y seprocede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que N.
Un número primo (positivo) es aquel número entero que sólo es divisiblepor sí mismo y por uno (y explícitamente se excluye al número 1 de la definición). Por ejemplo, 2, 3, 5, 7, 11, 13, 17, 19, 23… son números primos. Ningún número par, salvo el 2, puede ser primo(porque todos son también divisibles por 2). Pero ni 9, ni 15, ni 49 son primos, porque tienen otros divisores además de sí mismos y el número 1.
Se sabe que hay infinitos números primos (el primero encomprobarlo fue Euclides), pero lo maravilloso que hizo Eratóstenes fue construir un mecanismo que permite encontrarlos a todos (los primos).
Para eso, tuvo el ingenio de hacer lo siguiente:Eratóstenes, entonces, empezó a recorrer la lista. Tachó al número 1, porque él sabía que no era primo. Entonces, el primer número con el que se encontró, fue con el 2. Lo que hizo entonces, fue dejar el2 (que aquí aparece destacado) pero tachó todos los múltiplos de 2. Y le quedó una lista como ésta:
Una vez que tachó todos los múltiplos de 2, siguió con la lista y fue a buscar el primer númeroque no estaba tachado, en este caso el número 3. Lo dejó como estaba (sin tachar) pero eliminó a todos los múltiplos de 3. (O sea, tachó uno cada tres números.) Le quedó una tabla así:
Y siguió: nonecesitó tachar el 4, porque ya estaba tachado, pero siguió hasta el primer número que no lo estaba, y se encontró con el 5. Lo que hizo entonces fue tachar todos los múltiplos de 5. (Claro, ya...
La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado N. Se forma una tabla con todos los números naturalescomprendidos entre 2 y N y se van tachando los números que no son primos de la siguiente manera: cuando se encuentra un número entero que no ha sido tachado, ese número es declarado primo, y seprocede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que N.
Un número primo (positivo) es aquel número entero que sólo es divisiblepor sí mismo y por uno (y explícitamente se excluye al número 1 de la definición). Por ejemplo, 2, 3, 5, 7, 11, 13, 17, 19, 23… son números primos. Ningún número par, salvo el 2, puede ser primo(porque todos son también divisibles por 2). Pero ni 9, ni 15, ni 49 son primos, porque tienen otros divisores además de sí mismos y el número 1.
Se sabe que hay infinitos números primos (el primero encomprobarlo fue Euclides), pero lo maravilloso que hizo Eratóstenes fue construir un mecanismo que permite encontrarlos a todos (los primos).
Para eso, tuvo el ingenio de hacer lo siguiente:Eratóstenes, entonces, empezó a recorrer la lista. Tachó al número 1, porque él sabía que no era primo. Entonces, el primer número con el que se encontró, fue con el 2. Lo que hizo entonces, fue dejar el2 (que aquí aparece destacado) pero tachó todos los múltiplos de 2. Y le quedó una lista como ésta:
Una vez que tachó todos los múltiplos de 2, siguió con la lista y fue a buscar el primer númeroque no estaba tachado, en este caso el número 3. Lo dejó como estaba (sin tachar) pero eliminó a todos los múltiplos de 3. (O sea, tachó uno cada tres números.) Le quedó una tabla así:
Y siguió: nonecesitó tachar el 4, porque ya estaba tachado, pero siguió hasta el primer número que no lo estaba, y se encontró con el 5. Lo que hizo entonces fue tachar todos los múltiplos de 5. (Claro, ya...
Leer documento completo
Regístrate para leer el documento completo.