La criba de Eratóstenes: el algoritmo se usa para encontrar (identificar) los números primos en una lista. Consejo: comience eliminando de la lista los múltiplos de los números primos más pequeños

El matemático griego Eratóstenes (275 - 194 a. C.) utilizó un método nuevo y sencillo para determinar si los números de una lista son primos o no.
Empezó con los conocidos números primos pequeños 2, 3, 5, 7, 11, 13, 17, 23, etc. Está claro que todos sus múltiplos no son números primos sino compuestos.

Empezó por ordenar una lista de números naturales en orden ascendente. Luego identificó y eliminó todos los números compuestos más grandes de esta lista, ya que son múltiplos de los números primos más pequeños y, por lo tanto, separó los números primos más grandes de esta lista.
Ilustramos este método a continuación, con una lista de números ordenados en orden ascendente, del 2 al 100:

El número 2 es un número primo, por lo que primero identificamos todos los múltiplos de 2 en la lista:
2 × 2 = 4
2 × 3 = 6
2 × 4 = 8
2 × 5 = 10
2 × 6 = 12
2 × 7 = 14
2 × 8 = 16
2 × 9 = 18
2 × 10 = 20
... y así sucesivamente, hasta el número: 2 × 50 = 100.
El número 2 × 51 = 102, es mayor que 100, así que podemos parar.
Elimina todos los múltiplos del número 2 de la lista: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100.

El número 3 es un número primo, por lo que primero identificamos todos los múltiplos de 3 en la lista:
3 × 2 = 6 (Este número ya ha sido eliminado de la lista, es múltiplo de 2);
3 × 3 = 9
3 × 4 = 12 (Este número ya ha sido eliminado de la lista, es múltiplo de 2);
3 × 5 = 15
3 × 6 = 18 (Este número ya ha sido eliminado de la lista, es múltiplo de 2);
... y así sucesivamente, hasta el número: 3 × 33 = 99
El número 3 × 34 = 102, es mayor que 100, así que podemos parar.
Elimina todos los múltiplos del número 3 de la lista: 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 97, 99.
Si ya hemos quitado todos los múltiplos del número 2 de la lista, solo nos queda: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93. 99. Estos números se escriben a continuación, como múltiplos del número 3:
3 × 3 = 9
3 × 5 = 15
3 × 7 = 21
3 × 9 = 3 × 3 × 3 = 27
3 × 11 = 33
3 × 13 = 39
3 × 15 = 3 × 3 × 5 = 45
3 × 17 = 51
3 × 19 = 57
3 × 21 = 3 × 3 × 7 = 63
3 × 23 = 69
3 × 25 = 3 × 5 × 5 = 75
3 × 27 = 3 × 3 × 3 × 3 = 81
3 × 29 = 87
3 × 31 = 93
3 × 33 = 3 × 3 × 11 = 99.

Entonces procedemos con el siguiente número primo, 5:
5 × 2 = 10 (Este número ya se eliminó de la lista, es un múltiplo de 2);
5 × 3 = 15 (Este número ya se eliminó de la lista, es un múltiplo de 3);
5 × 4 = 20 (Este número ya se eliminó de la lista, es un múltiplo de 2);
5 × 5 = 25
5 × 6 = 30 (Este número ya se eliminó de la lista, es un múltiplo de 2 y 3);
5 × 7 = 35
... y así sucesivamente, hasta el número: 5 × 20 = 100 (Este número ya se eliminó de la lista, es un múltiplo de 2).
El número 5 × 21 = 105, es mayor que 100, así que podemos parar.
Elimina todos los múltiplos del número 5 de la lista: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100.
Si no nos estamos ocupando de los múltiplos de 2 y 3, que ya se han eliminado de la lista, todavía nos quedan estos números para eliminar: 25, 35, 55, 65, 85, 95, es decir. exactamente aquellos números que tienen en su descomposición en factores primos solo factores primos mayores o iguales a 5
5 × 5 = 25
5 × 7 = 35
5 × 11 = 55
5 × 13 = 65
5 × 17 = 85
5 × 19 = 95.

$inc_text3='

Entonces procedemos con el siguiente número primo, 7:
7 × 2 = 14 (el número ya ha sido eliminado de la lista - es un múltiplo de 2);
7 × 3 = 21 (el número ya ha sido eliminado de la lista - es un múltiplo de 3);
7 × 4 = 28 (el número ya ha sido eliminado de la lista - es un múltiplo de 2);
7 × 5 = 35 (el número ya ha sido eliminado de la lista - es un múltiplo de 5);
7 × 6 = 42 (el número ya ha sido eliminado de la lista - es un múltiplo de 2 y 3);
7 × 7 = 49
... y así sucesivamente, hasta el número: 7 × 14 = 98 (el número ya ha sido eliminado de la lista - es un múltiplo de 2).
7 × 15 = 105, es mayor que 100, así que podemos parar.
Elimina todos los múltiplos del número 7 de la lista: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.
Si no nos fijamos en los múltiplos de 2, 3 y 5, que ya han sido eliminados de la lista, todavía tenemos que eliminar: 49, 77, 91. Estos son precisamente los números que tienen en sus factores primos primos factores mayores o iguales a 7:
7 × 7 = 49
7 × 11 = 77
7 × 13 = 91.

El siguiente número primo en la lista es 11 y debemos eliminar los múltiplos de 11 de la lista.
Sin embargo, como vimos en los pasos anteriores, solo debemos intentar eliminar de la lista los números que tienen en su descomposición factores primos que son mayores o iguales a 11.
Pero ya 11 × 11 = 121, que es mayor que 100.
Esto significa que todos los números que quedaron en la lista después de realizar los pasos anteriores ya son números primos.

La lista de números primos consiste en los números que no se eliminan.
Después de quitar de la lista todos los múltiplos de los números primos 2, 3, 5 y 7, nos quedamos en la lista con estos números: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 - la lista de los numeros primos del 2 al 100.

Algunos artículos sobre los números primos