Tamiz de Eratóstenes – Algoritmo de números primos

Tamiz de Eratóstenes – Algoritmo de números primos

La criba de Eratóstenes es una técnica formulada por un brillante matemático griego, Eratóstenes, cuyos esfuerzos contribuyeron en gran medida a la identificación de los números primos.

Hizo una gran contribución a las matemáticas, y el descubrimiento de la criba fue lo mejor que había hecho en este campo. Es un patrón o algoritmo que funciona eliminando números que no encajan en un escenario.

¿Qué es el Tamiz de Eratóstenes?

La criba de Eratóstenes es un algoritmo matemático para encontrar números primos entre dos conjuntos de números.

Los patrones de tamiz de Eratóstenes funcionan tamizando o eliminando números dados que no cumplen con un criterio determinado. En este caso, el modelo elimina múltiplos de números primos conocidos.

Algoritmo de números primos

Un número primo es un número entero positivo o un número entero mayor que 1, que solo es divisible por 1 y por sí mismo. El algoritmo de números primos es un programa que se utiliza para encontrar números primos tamizando o eliminando números compuestos. El algoritmo facilita el trabajo al eliminar complejas divisiones o multiplicaciones en bucle.

Estos son los pasos que se usan para encontrar números primos iguales o menores que un número entero η.

  • Haz una lista de todos los números consecutivos del 2 al η, es decir (2, 3, 4, 5, ……, η).
  • Asignar la primera letra del número primo pags.
  • Empezando con pags2hacer un incremento de pags y marcar enteros iguales o mayores que pags2 en el algoritmo. Estos números enteros serán pags(pags +1), pags(pag + 2), pags(pags +3), pags(pags + 4)…
  • El primer número sin marcar mayor que pags se identifica en la lista. Si el número no existe en la lista, el procedimiento se interrumpe. pags es igual al número y se repite el paso 3.
  • El tamiz de Eratóstenes se detiene cuando el cuadrado del número probado excede el último número de la lista.
  • Todos los números en la lista sin marcar al final del algoritmo se llaman números primos.

Ejemplo 1

Escribe todos los números primos menores o iguales a 30.

Solución

  • Paso 1: El primer paso es hacer una lista de todos los números.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 y 30.

  • Paso 2: escribir audaz todos los múltiplos de 2, excepto el propio 2.

2, 3, 45, 6 siete , 89, diez,11, 1213, 1415, dieciséis17 años, 1819 años, 2021, 2223, 2425, 2627, 2829, y 30.

  • Paso 3: El siguiente número sin sombrear es 3. Escribe su cuadrado (32 = 9) en negrita.

2, 3, 45, 6 siete , 8, 9, diez,11, 1213, 14, 15, dieciséis17 años, 1819 años, 20, 21, 2223, 2425, 26, 27, 2829, y 30.

  • Paso 4: Ahora el tercer número sin sombrear es 5. Escribe su cuadrado 52=25 en negrita.

2, 3, 45, 6 siete , 8, 9, diez,11, 1213, 14, 15, dieciséis17 años, 1819 años, 20, 21, 2223, 24, 25, 26, 27, 2829, y 30.

  • Paso 5: El cuarto número sin sombrear es 7 y mayor que la raíz cuadrada de 30.
    Por lo tanto, ya no quedan múltiplos de 7 ya que fueron eliminados por 2 y 3 como 14, 28 y 21 respectivamente. Los números restantes 2, 3, 5, 7, 11, 13, 17, 19, 23 y 29 son primos.

Ejemplo 2

Encuentra números primos entre 1 y 100 usando el algoritmo de Eratóstenes.

Solución

  1. Paso 1: Los números entre 1 y 100 se enumeran en la siguiente tabla.
1 2 3 4 5 6 siete 8 9 diez
11 12 13 14 15 dieciséis 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 sesenta y cinco 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
  • Paso 2: El siguiente paso es escribir audaz todos los múltiplos de 2, excepto el propio 2.
1 2 3 4 5 6 siete 8 9 diez
11 12 13 14 15 dieciséis 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 sesenta y cinco 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
  • Paso 3: Ahora audaz todos los múltiplos de 3, 5 y 7 y dejar sólo esos números.
1 2 3 4 5 6 siete 8 9 diez
11 12 13 14 15 dieciséis 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 sesenta y cinco 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
  • Paso 4: Dado que los múltiplos de 11, 13, 17 y 19 no están presentes en la lista, el 1 finalmente se sombrea porque no es primo.
1 2 3 4 5 6 siete 8 9 diez
11 12 13 14 15 dieciséis 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 sesenta y cinco 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
  • Paso 5: Los números sin sombrear son primos. Incluyen:

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.