Tamiz de Eratosthenes con C ++

Un número primo es un número natural (completo) que es mayor o igual a dos, que solo se puede dividir por sí mismo y 1. Los primeros números primos son: 2, 3, 5, 7, etc.

Para el número 5, el número de números primos que están a la altura y/o incluido 5 son:

2, 3, 5

Para el número 8, el número de números primos que están a la altura y/o incluyen 8 son:

2, 3, 5, 7

Para el número 19, el número de números primos que están a la altura y/o incluyen 19 son:

2, 3, 5, 7, 11, 13, 17, 19

Para el número 25, el número de números primos que están a la altura y/o incluido 25 son:

2, 3, 5, 7, 11, 13, 17, 19, 23

Para el número 36, el número de números primos que están a la altura y/o incluido 36 son:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Para el número 37, el número de números primos que están a la altura y/o incluido 37 son:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37

Estas listas son solo ejemplos. Hay muchas otras listas de ejemplo de números primos a continuación y/o incluir un número determinado. Comience la comprensión del tamiz de Eratosthenes observando que los números primos por debajo de un número dado más pequeño son los mismos que la primera parte de los números primos por debajo de un número más grande dado.

El tamiz de Eratosthenes es una técnica para encontrar todos los números primos que son menores o iguales a un número dado, como 36 o 37 arriba. Este número como 36 o 37 generalmente se le da el nombre de la variable "n" en la programación. El tamiz de Eratosthenes se considera un algoritmo eficiente para obtener la lista de números primos.

Demostración para tamiz de eratóstenes

La pregunta es: encontrar los números primos menos o igual a 5, por ejemplo, de manera eficiente. La forma eficiente aquí significa usar la menor cantidad de operaciones posible. Los números primos comienzan desde 2. Todos los números, incluidos los múltiplos de pequeños números primos de 2 a 5, son:

2, 3, 4, 5

En este rango, un número que no es un número primo es un múltiplo de un número primo anterior. Se puede obtener un múltiplo mediante la adición del mismo número primo, una y otra vez. Por ejemplo, 2 + 2 es 4, más 2 nuevamente es 6. Y eso sigue más allá del rango. Cuatro, que es un múltiplo de 2, no debe estar en la lista porque no es un número primo. La ecuación 3 + 3 es 6, que ya está más allá del rango. Y 6 o cualquier número más allá del rango no debe estar en la lista. Entonces, el resultado es el siguiente:

2, 3, 5

El número en cuestión aquí es 5. La raíz cuadrada de 5 es 2.24. El valor entero para la raíz cuadrada de 5 es 2. Los múltiplos de los números primos a continuación y hasta 2, que es el valor entero para la raíz cuadrada de 5, se eliminan de la lista de todos los números.

Considere ahora el número 8. Todos los números, incluidos los múltiplos de pequeños números primos de 2 a 8, son:

2, 3, 4, 5, 6, 7, 8

La ecuación 2 + 2 es 4. Cuatro salen. La ecuación 4+2 es 6. Seis salen. La ecuación 6 + 2 es 8. Ocho está fuera. El siguiente número primo a considerar es 3. La ecuación 3 + 3 es 6. Seis ya está descartado por la adición continua de 2. La ecuación 6 + 3 es 9; que está fuera de rango. Los números primos entre 2 y 8, inclusive, son:

2, 3, 5, 7

El número en cuestión aquí es 8. La raíz cuadrada de 8 es 2.83. El valor entero para la raíz cuadrada de 8 es 2. Los múltiplos de los números primos a continuación y hasta 2, que es el valor entero para la raíz cuadrada de 8 se eliminan para obtener la lista requerida de números primos.

Un problema similar es enumerar los números primos de 2 a 19, inclusivamente. Todos los números de 2 a 19, inclusive son:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

La ecuación 2 + 2 es 4; 4 está fuera. La ecuación 4 + 2 es 6; 6 está fuera. La ecuación 6 + 2 es 8; 8 está fuera. La ecuación 8 + 2 es 10; 10 está fuera. La ecuación 10 + 2 es 12; 12 está fuera. La ecuación 12 + 2 es 14; 14 está fuera. La ecuación 14 + 2 es 16; 16 está fuera. La ecuación 16 + 2 es 18; 18 está fuera. La ecuación 18 + 2 es 20, que está por encima del rango; 20 está fuera.

El próximo número primo a considerar, ir hacia la raíz cuadrada de 19, es 3. La ecuación 3 + 3 es 6; 6 ya está descartado como un múltiplo de 2. La ecuación 6 + 3 es 9; 9 sale. La ecuación 9 + 3 es 12; 12 ya está descartado como un múltiplo de 2. La ecuación 12 + 3 es 15; 15 está fuera. La ecuación 15 + 3 es 18; 18 ya está descartado como un múltiplo de 2. La ecuación 18 + 3 es 21, que está por encima del rango. El resultado es:

2, 3, 5, 7, 11, 13, 17, 19

El número en cuestión aquí es 19. La raíz cuadrada de 19 es 4.36. El valor entero para la raíz cuadrada de 19 es 4. Se eliminan los múltiplos de los números primos a continuación y hasta 4, que es el valor entero de la raíz cuadrada de 19.

Los números primos a continuación y hasta 4 son: 2 y 3. Debido a 3, no tenía sentido eliminar los números 6, 12 y 18 que son múltiplos de 3, que ya se eliminan como múltiplos de 2. Solo los múltiplos de 3 que no son múltiplos de 2 se eliminan debido a 3. En la práctica, después de eliminar los múltiplos de 2, solo los múltiplos desde y por encima de 3 x 3 = 9 deben eliminarse sin repetir la eliminación de 6. Debido a 3, los números que se eliminarán son 9, 12, 15 y 18; con 12 y 18 eliminados dos veces en teoría. El número 6 debe eliminarse una vez y no dos veces.

Sea N 25, un nuevo número en cuestión. Todos los números de 2 a 25 son:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

La ecuación 2 + 2 es 4; 4 sale. La ecuación 4 + 2 es 6; 6 está fuera. La ecuación 6 + 2 es 8; 8 está fuera. La ecuación 8 + 2 es 10; 10 está fuera. La ecuación 10 + 2 es 12; 12 está fuera. La ecuación 12 + 2 es 14; 14 está fuera. La ecuación 14 + 2 es 16; 16 está fuera. La ecuación 16 + 2 es 18; 18 está fuera. La ecuación 18 + 2 es 20; 20 está fuera. La ecuación 20 + 2 es 22; 22 está fuera. La ecuación 22 + 2 es 24; 24 está fuera. La ecuación 24 + 2 es 26, que está por encima del rango.

El siguiente número primo a considerar, ir hacia la raíz cuadrada de 25, es 3. La ecuación 3 + 3 es 6; 6 ya está descartado como un múltiplo de 2. La ecuación 6 + 3 es 9; 9 sale. La ecuación 9 + 3 es 12. Doce ya está descartado como un múltiplo de 2. La ecuación 12 + 3 es 15; 15 está fuera. La ecuación 15 + 3 es 18; 18 ya está descartado como un múltiplo de 2. La ecuación 18 + 3 es 21; 21 sale. La ecuación 21 + 3 es 24; 24 ya está descartado como un múltiplo de 2. La ecuación 24 + 3 es 27, que está por encima del rango.

El siguiente número primo a considerar, ir hacia la raíz cuadrada de 25, que es 5, es 5. La ecuación 5 + 5 es 10; 10 ya está descartado como un múltiplo de 2. La ecuación 10 + 5 es 15; 15 ya está descartado como un múltiplo de 3. La ecuación 15 + 5 es 20; 20 ya está descartado como un múltiplo de 2. La ecuación 20 + 5 es 25; 25 sale. El resultado es:

2, 3, 5, 7, 11, 13, 17, 19, 23

El número en cuestión aquí es 25. La raíz cuadrada de 25 es 5. El valor entero para la raíz cuadrada de 25 es 5. Se eliminan los múltiplos de los números primos a continuación y hasta 5, que es el valor entero para la raíz cuadrada de 25.

Los números primos a continuación y hasta 5 son 2, 3 y 5. Debido a 2, los números que se supone que se eliminarán de la lista de todos los números por múltiplos son: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 y 24. Debido a 3, los números que se supone que se eliminarán de la lista por múltiplos son: 6, 9, 12, 15, 18, 21 y 24. Debido a 5, los números que se supone que deben ser eliminados por múltiplos son: 10, 15, 20 y 25.

Por todos los múltiplos, las mudanzas son las siguientes:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 6, 9, 12, 15, 18, 21, 24

5: 10, 15, 20, 25

Por múltiplos, 6 se elimina dos veces (en teoría), 10 se elimina dos veces (en teoría), 12 se elimina dos veces (en teoría), 15 se elimina dos veces (en teoría), 20 se elimina dos veces (en teoría), y 24 se elimina dos veces (en teoría).

Sin embargo, si se debe a 3, la eliminación comienza de 3 x 3 = 9, entonces 6 se elimina solo una vez. Si se debe a 5, la eliminación comienza de 5 x 5 = 25, entonces la eliminación de 10, 15 y 20 se realiza una vez cada uno. Sin embargo, la eliminación de 12, 18 y 24 todavía se realiza dos veces por número. Aún así, habría alguna ventaja, ya que se omiten cuatro operaciones repetidas de eliminación (para 6, 10, 15 y 20). Esto mejora la eficiencia (complejidad del tiempo). Con eso, las mudanzas serán:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 9, 12, 15, 18, 21, 24

5: 25

Los números 6, 10, 15 y 20 se han eliminado una vez, en lugar de dos veces. Los números, 12, 18 y 24 se han eliminado dos veces. A partir de ahora, no se puede hacer nada para eliminar 12, 18 y 24 solo una vez.

Las situaciones para los números 36 y 37, o cualquier otro número mayor que 1, se explican de manera similar.

Evitar la redundancia

Simplemente eliminando los múltiplos de números primos de 2 al valor entero de √n, se obtiene el conjunto requerido de números primos. La eficiencia se puede mejorar eliminando los múltiplos de los números primos, comenzando desde el cuadrado del número primo (i²) hasta el valor entero de √n como se sugirió anteriormente. Esto omite algunas operaciones de eliminación de números. Entonces, reduciendo el número total de operaciones. El tamiz de Eratosthenes se realiza mediante este segundo enfoque.

Algoritmo de tamiz de Eratóstenes

El algoritmo comienza haciendo un vector indexado de longitud basado en cero que es n+1. Cada elemento de este vector se inicializa a booleano, verdadero, excepto los primeros y segundos elementos para el índice 0 y el índice 1 que se inicializan en FALSO. Para este vector, el índice 2 corresponde al número (Prime) 2; El índice 3 corresponde al número (Prime) 3; El índice 4 corresponde al número 4; etcétera. Dado que el vector es cero índice basado en A, la longitud debe ser n+1 para que el último índice corresponda a n.

Un número de índice para esta lista de vectores que debe eliminarse no se elimina per se: el valor del número de índice se hace falso para indicar la eliminación. Es decir, el elemento tiene el valor falso. Entonces, si un número (índice) debe eliminarse de la lista (vector) más de una vez, el valor para el índice se hace falso más de una vez.

Al final, los índices para los elementos del vector cuyos valores se mantuvieron verdaderos se leen como los números primos.

Antes de eso, los múltiplos de los índices principales que comienzan desde el cuadrado del índice principal (i²) hasta el valor entero de √n están marcados como falsos.

Codificación de C ++

El programa en C ++ debe comenzar con lo siguiente:

#incluir
#incluir
usando el espacio de nombres STD;

El tamiz de la función Eratosthenes es el siguiente:

vector tamiz (int n)
vector tamiz (n+1, verdadero);
tamiz [0] = falso;
tamiz [1] = falso;
int i = 2;
mientras (yo * yo <= n)
if (tamizar [i] == true) // Si yo es un número primo
int j = i * i;
mientras (J <= n) //marking multiples with false
tamiz [j] = falso;
j = j + i; // incremento por múltiples


i = i + 1; // Incremento normal del bucle exterior, por 1

Tamiz de regreso;

Lea los comentarios del código. El nombre de la función es Sieve (). El vector devuelto, después de que todos los múltiplos se marcan como falsos, también se llama tamiz. Una función principal de C ++ adecuada para este código es:

int main (int argc, char ** argv)

vector vtr = tamiz (37);
para (int i = 0; iif (vtr [i] == verdadero)
cout << i << ";
cout << endl;
regresar 0;

Con este código, la salida es la siguiente:

2 3 5 7 11 13 17 19 23 29 31 37

La complejidad del tiempo para esta función es o (n log n).

Conclusión

El algoritmo comienza haciendo un vector indexado basado en cero de la longitud n+1. Cada elemento de este vector se inicializa a booleano, verdadero, excepto los primeros y segundos elementos para el índice 0 y el índice 1 que se inicializan en FALSO. Para este vector, cada índice es una serie de interés. Dado que el vector está basado en cero indexado, la longitud debe ser n+1 para que el último índice sea n.

El valor del número que es el índice se hace falso para indicar la eliminación. Es decir, el elemento tiene el valor falso.

Al final, los índices para los elementos del vector cuyos valores se mantuvieron verdaderos se leen como los números primos.

Antes de eso, los múltiplos de los índices principales que comienzan desde el cuadrado del índice principal hasta el valor entero de √n se marcan como falsos.