Números primos y compuestos | Criba de Eratóstenes.

Números primos y compuestos | Criba de Eratóstenes.

Antes de empezar, refresquemos conceptos:

• Número compuesto: Número con 1 o más divisores aparte de 1 y sobre el mismo.

• Número primo: Número con únicamente 2 divisores: 1 y el mismo.

Criterios de divisibilidad.

• 2: Aplica a todos los números par.

• 3: Aplica a números que al sumar sus dígitos sean múltiplos de 3.

• 5: Aplica a números terminados en 5 y 0.

• 7: Aplica a números que, restando el último dígito multiplicado por 2 al resto de dígitos sobrantes, de como resultado un número múltiplo de 7. Ej: 595: 59 - (5*2)= 49

Criba de Eratóstenes

Consiste en un método para encontrar los números primos en determinada cantidad "n" dada de números naturales. Para ello, se escriben los números naturales entre 2 y "n" en una tabla, creando filas a cada 10 números (o cualquiera que preferiblemente acabe en 0 o 5). 

Empezando por el 2, que se toma como número primo, se marcan todos los múltiplos de 2 dentro de la tabla. Y así se continua el mismo proceso con los números siguientes, tales como el 3, 5, 7, etc. Todo ello en base a los criterios de divisibilidad para efectuarlo de manera más práctica.

Para saber hasta que número máximo se debe de repetir este proceso, se toma dicho numero y se eleva al cuadrado. Si el resultado es mayor a "n", ya no se toma en cuenta y se termina el proceso (ya que los múltiplos de dicho número ya estarán tachados).

Los números restantes no tachados son todos los números primos en el intervalo de 2 - "n". 

El 1 no se toma en cuenta.

Fotos: Ejemplo con Criba de 2 a 100.

Rojo: Múltiplos de 2

Amarillo: Múltiplos de 3

Verde: Múltiplos de 5

Azul: Múltiplos de 7

Magenta: Múltiplos de 11 (Ya aparecen tachados, porque 11² >100).

Los números en blanco son todos los números primos.

Algo interesante del método, es que al estar ordenado en una tabla, se aprecian patrones al momento de estar tachando. Para múltiplos de 2 y 5 siempre en verticales, 3 en diagonales, 7 en diagonal dejando una fila de por medio y así.

PD: ¿Por qué no supe esto en la primaria?.

Link con mas información:

https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes

Linnk para interactuar con cibra:
http://www.visnos.com/demos/sieve-of-eratosthenes

Gracias por leer.