Download Criba de Eratóstenes

Survey
yes no Was this document useful for you?
   Thank you for your participation!

* Your assessment is very important for improving the work of artificial intelligence, which forms the content of this project

Document related concepts

Criba de Eratóstenes wikipedia, lookup

Criba de Atkin wikipedia, lookup

Criba de Legendre wikipedia, lookup

Número de la suerte wikipedia, lookup

Test de primalidad AKS wikipedia, lookup

Transcript
Criba de Eratóstenes
Eratóstenes nació en Cyrene (ahora Libia), en el norte de Africa. Vivió entre los años
275 y 195 antes de Cristo. Por varias décadas, fue el director de la famosa Biblioteca de
Alejandría. Fue una de las personas más reconocidas de la época, pero lamentablemente sólo
pocos fragmentos de lo que escribió sobrevivieron en el tiempo.
Eratóstenes se hizo famoso por dos cosas que hizo:
–por la medición increíblemente precisa que hizo del diámetro de la Tierra, y
–por haber fabricado una criba, o un filtro, para descubrir todos los números primos.
Vamos a ver qué es esto de los números primos!!!
Un número primo es aquel número que sólo es divisible por 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).
Se sabe que hay infinitos números primos (el primero en comprobarlo 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... (Podemos imprimir la siguiente tabla y
hacerlo...)
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 el 2 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úmero que 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.)
Y siguió: no necesitó 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 había habido algunos que había tachado antes, pero siguió con los
que estaban libres.) De esta forma, quedaron eliminados todos los múltiplos de 5.
Y luego, siguió con el 7, y tachó todos los múltiplos de 7. Y luego, siguió hasta el primer
número no tachado, y encontró el 11. Y luego, tachó todos los múltiplos de 11. Y siguió hasta
encontrar, luego, al primer número no tachado. Y se encontró con el 13. Y luego, tachó todos
los múltiplos de 13 y siguió con este mecanismo. Finalmente, los números que no quedaban
tachados en ningún paso, es porque no eran múltiplos de ningún número anterior. Con ésos se
quedaba Eratóstenes. En realidad, lo que estaba haciendo era construir una suerte de “filtro”
por el cual, al hacer pasar a todos los números, sólo quedaban los “primos”.
Y la lista quedaba así:
Todos los números primos que hay entre los primeros cien números, son: 2, 3, 5, 7,
11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 59, 61, 67, 71, 73, 79, 83, 89, 91 y 97