Criba de Eratóstenes: el algoritmo para encontrar los números primos en una lista; retirar los múltiplos de los números primos más pequeños

El matemático griego ERATOSTENE (275 - 194 aC) ha aplicado un método novedoso y fácil para determinar si los números en una lista son primos o no. Partiendo de los números pequeños conocidos, 2, 3, 5, 7, 11, 13, 17, 21, etc., está claro que todos sus múltiplos no son números primos sino compuestos. Ordenó una lista de números naturales en orden ascendente y luego eliminó todos los múltiplos de los primeros números primos para identificar el resto de los números primos más grandes en esa lista. Ejemplificaremos este método a continuación en una lista de números que van del 2 al 100:

  • El número 2 es primo, por lo que eliminamos de esta cadena de números todos los múltiplos de 2: 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 2 × 50 = 100. 2 × 51 = 102, es mayor que 100, así que nos detenemos.
  • Múltiplos de 2 para eliminar 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 (números de dos por dos).
  • 3 es el siguiente número primo, por lo que eliminaremos de la lista todos los múltiplos de 3: 3 × 2 = 6 (que ya se ha eliminado de la lista, que es un múltiplo de 2); 3 × 3 = 9; 3 × 4 = 12 (que ya ha sido eliminado de la lista, siendo un múltiplo de 2); 3 × 5 = 15; 3 × 6 = 18 (que ya ha sido eliminado de la lista, siendo un múltiplo de 2); ... y así sucesivamente hasta: 3 × 33 = 99. 3 × 34 = 102, es mayor que 100, así que nos detenemos.
  • Múltiplos de 3 para eliminar 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 (números de tres por tres). Si no vemos los múltiplos de 2 que ya han sido eliminados de la lista, todavía tenemos: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, es decir. números que tienen como factores solo números primos mayores o iguales a 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.
  • También procederemos con el siguiente número primo, 5: 5 × 2 = 10 (que ya ha sido eliminado de la lista, siendo un múltiplo de 2); 5 × 3 = 15 (que ya ha sido eliminado de la lista, siendo un múltiplo de 3); 5 × 4 = 20 (que ya ha sido eliminado de la lista, siendo un múltiplo de 2); 5 × 5 = 25; 5 × 6 = 30 (que ya ha sido eliminado de la lista, siendo ambos un múltiplo de 2 y 3); 5 × 7 = 35; ... y así sucesivamente hasta: 5 × 20 = 100 (que ya ha sido eliminado de la lista, siendo un múltiplo de 2). 5 × 21 = 105, es mayor que 100, así que nos detenemos.
  • Múltiplos de 5 para eliminar de la lista: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 (números de cinco por cinco). Si no miramos los múltiplos de 2 y 3, que ya han sido eliminados de la lista, todavía tenemos que eliminar: 25, 35, 55, 65, 85, 95, es decir. exactamente los números que tienen como factores solo números primos mayores o iguales a 5: 5 × 5 = 25; 5 × 7 = 35; 5 × 11 = 55; 5 × 13 = 65; 5 × 17 = 85; 5 × 19 = 95.
  • Luego hacemos lo mismo con el siguiente número primo, 7: 7 × 2 = 14 (que ya ha sido eliminado de la lista, siendo un múltiplo de 2); 7 × 3 = 21 (que ya ha sido eliminado de la lista, siendo un múltiplo de 3); 7 × 4 = 28 (que ya ha sido eliminado de la lista, siendo un múltiplo de 2); 7 × 5 = 35 (que ya ha sido eliminado de la lista, siendo un múltiplo de 5); 7 × 6 = 42 (que ya ha sido eliminado de la lista, siendo ambos un múltiplo de 2 y 3); ... 7 × 7 = 49; ... y así sucesivamente hasta: 7 × 14 = 98 (que ya ha sido eliminado de la lista, siendo un múltiplo de 2). 7 × 15 = 105, es mayor que 100, así que nos detenemos.
  • Múltiplos de 7 para eliminar de la lista: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98 (números de siete por siete). Si no miramos los múltiplos de 2, 3 y 5, que ya han sido eliminados de la lista, todavía tenemos que eliminar: 49, 77, 91, es decir. exactamente los números que tienen como divisores solo números primos 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 de la lista los múltiplos de 11; Sin embargo, como hemos visto anteriormente, solo deberíamos eliminar de la lista los números que tienen como divisores solo números primos mayores que o iguales a 11. Pero ya 11 × 11 = 121 es mayor que 100, significa que todos los números que quedan en la lista después del proceso descrito anteriormente ya son números primos.
  • Después de eliminar de la lista todos los múltiplos de los números primos: 2, 3, 5 y 7, todavía tenemos en la lista: 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, es decir, la lista de los números primos del 2 al 100.

¿Qué es un número primo?

¿Qué es un número compuesto?

Números primos hasta 1.000

Números primos hasta 10.000

Criba de Eratóstenes

Algoritmo de Euclides

Reducir fracciones matemáticas ordinarias para reducir los términos (simplificando): pasos y ejemplos