"Ayúdame a hacerlo por mí mismo.“ María Montessori.

miércoles, 18 de octubre de 2017

La criba de Eratóstenes.

Criba de Eratóstenes
El matemático griego Eratóstenes ( siglo III a.C.) ideó una manera rápida de obtener todos los números primos hasta uno concreto. Se trata de un procedimiento denominado Criba de Eratóstenes, que veremos cómo funciona encontrando todos los números primos entre 1 y 100.
Teniendo todos los números en una tabla, se trata de ir buscando los que sean múltiplos de algún número y por tanto sean compuestos, para descartarlos como primos. Los números que nos queden sin descartar, serán declarados números primos.
La criba de Eratóstenes se para en el momento en que el cuadrado del número a investigar es mayor que el último número de la lista (en nuestro caso el 100).
Como 11 = 121 y 121>100, cuando lleguemos al número 11, podremos parar de buscar.
Números primos entre 1 y 100 con la Criba de Eratóstenes
Empezamos colocando los números del 1 al 100 en una tabla como esta, donde resulta muy fácil observar los patrones que forman los múltiplos de cada número. Marcamos el 1, que no se considera un número primo.
números primos
  • Primero, buscamos los múltiplos de 2 y los marcamos (exceptuando el 2, que sabemos que sólo tiene como divisores 1 y 2, así que es primo). Todos estos números serán compuestos. ¿Has visto qué patrón tan bonito tienen los números pares?
números primos
  • Ahora, de los que quedan, buscamos los múltiplos de 3 y los marcamos (exceptuando el 3, que es primo). Una manera fácil es ir contando de 3 en 3. También aquí observamos un patrón interesante.
números primos
  • Ahora es el turno de buscar los múltiplos de 5 (de 4 no haría falta, porque todos los múltiplos de 4 también son múltiplos de 2, así que ya los hemos marcado anteriormente). Es fácil encontrarlos, ya que son todos los acabados en 0 o 5. Dejamos el 5 sin marcar, ya que es primo.
números primos
  • Vamos ahora con los múltiplos de 7 (los de 6 no hace falta buscarlos, ya que 6 = 2 x 3 y ya hemos buscado los de 2 y 3). Dejamos el 7 sin marcar, ya que es primo.
números primos
Como ya solo nos queda buscar los múltiplos de 8, 9 y 10 y éstos son compuestos y múltiplos de números que ya hemos buscado, llegamos al número 11, donde dijimos al principio que debíamos parar. ¡Así que ya hemos terminado!
Lista de números primos entre 1 y 100
Podemos determinar entonces que los números que nos han quedado sin marcar, son todos números primos. Así que ya tenemos la lista de números primos entre 1 y 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97.

Por último, aquí tienes una imagen con los pasos del ejemplo que hemos visto, para que los tengas todos juntos.
números primos

0 comentarios:

Publicar un comentario

Aquí puedes dejar tus dudas, comentarios, sugerencias...
Por favor, utiliza un lenguaje apropiado, y no escribas en mayúsculas. Si no cumples esta norma, tu comentario será retirado.