La
Criba de Erastotenes
Un numero primo es aquel que sólo es divisible por 1 y por sí mismo. Algo tan sencillo
como eso; lo complicado es que no existe una fórmula matemática que
asegure si lo es o no.
Pensemos en un número elevado como 191.587, ¡no tenemos una fórmula que determine si este número es primo!
Tendríamos que ir comprobando si tiene algún divisor y por lo tanto es compuesto. En ese caso, lo descartaríamos como número primo.
Para los primeros números primos (2, 3, 5, 7, 11), sería asequible comprobar si tienen divisores con ayuda los criterios de divisibilidad, pero para números más altos ya no sería tan fácil.
El matemático griego Erastotenes( 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 Erastotenes, 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 112 = 121 y 121>100, cuando lleguemos al número 11, podremos parar de buscar.
Pensemos en un número elevado como 191.587, ¡no tenemos una fórmula que determine si este número es primo!
Tendríamos que ir comprobando si tiene algún divisor y por lo tanto es compuesto. En ese caso, lo descartaríamos como número primo.
Para los primeros números primos (2, 3, 5, 7, 11), sería asequible comprobar si tienen divisores con ayuda los criterios de divisibilidad, pero para números más altos ya no sería tan fácil.
El matemático griego Erastotenes( 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 Erastotenes, 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 112 = 121 y 121>100, cuando lleguemos al número 11, podremos parar de buscar.
