Algoritmo de tamiz de Eratóstenes en C++

Este artículo explicará cómo implementar el algoritmo de tamiz de eratóstenes en C++.

Implementar el algoritmo Sieve of Eratosthenes usando el contenedor std::vector en C++

El tamiz de Eratóstenes es uno de los tamices de números primos, que representa algoritmos relativamente eficientes para encontrar números primos. Existen múltiples algoritmos adecuados para diferentes rangos de números primos y también tienen características de rendimiento contrastantes.

El tamiz de Eratóstenes puede considerarse el más fácil de implementar y es bastante eficiente en rangos más pequeños. Aunque su complejidad de tiempo de ejecución es O(N loglogN), funciona mejor en rangos más pequeños.

Este artículo implementará este algoritmo utilizando el método más sencillo para adaptarse al artículo introductorio. El algoritmo toma el valor entero y encuentra todos los números primos menores o iguales al entero dado.

Al principio, construimos un array de valores booleanos que tiene el mismo tamaño que el entero dado e inicializamos cada elemento para que tenga un valor true.

Luego iteramos a través de esta matriz de elementos y almacenamos un valor false si el elemento dado tiene un índice compuesto. Accedemos a los índices del array calculando los múltiplos de primos consecutivos comenzando desde el más pequeño - 2, y detenemos la iteración una vez que el cuadrado del primo dado es mayor que el entero de entrada - n. Los pasos anteriores se implementan utilizando los bucles for anidados en la función printPrimesLessThanN.

Finalmente, recorremos este vector e imprimimos los índices de elementos que tienen un valor true almacenado. Tenga en cuenta que la última operación es manejada por el bucle for al final de la función printPrimesLessThanN. También proporcionamos el código del controlador en la función main para aceptar el número entero que denota el límite superior del usuario y validar la entrada hasta que se pasa a la función printPrimesLessThanN.

#include <cstring>
#include <iostream>
#include <limits>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;

void printPrimesLessThanN(unsigned long long n) {
  vector<bool> table(n, true);

  for (unsigned long long p = 2; p * p < n; p++) {
    if (table[p] == true) {
      for (unsigned long long i = p * p; i < n; i += p) table[i] = false;
    }
  }

  for (unsigned long long p = 2; p < n; p++)
    if (table[p]) cout << p << " ";
}

int main() {
  unsigned long long integer;

  while (true) {
    cout << "Enter integer: ";
    if (cin >> integer) {
      break;
    } else {
      cout << "Enter a valid integer value!\n";
      cin.clear();
      cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }
  }

  cout << "Following prime numbers are smaller than given integer: \n";

  printPrimesLessThanN(integer);

  return EXIT_SUCCESS;
}

Producción :

Enter integer: 30
Following prime numbers are smaller than given integer:
2 3 5 7 11 13 17 19 23 29

El fragmento de código anterior es un ejemplo funcional que se puede optimizar con varios métodos, como explotar la simultaneidad en el programa, dividir y almacenar el array en la memoria para optimizar el acceso a los datos o utilizar otros conocimientos algorítmicos. Sin embargo, hay una pequeña idea que puede ahorrar múltiplos de tiempo de ejecución para esta implementación sin hacer grandes cambios, y es almacenar valores true / false en el vector de char.

Como puede observar al ejecutar múltiples pruebas en números más grandes, el tipo bool funciona bastante peor que el tipo integral como char o incluso int. El siguiente ejemplo de código muestra el escenario de referencia simple para ambas versiones de la función - printPrimesLessThanN e imprime el tiempo transcurrido al final del programa.

#include <sys/time.h>

#include <cstring>
#include <iostream>
#include <limits>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;

float time_diff(struct timeval *start, struct timeval *end) {
  return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}

void printPrimesLessThanN(unsigned long long n) {
  vector<bool> table(n, true);
  struct timeval start {};
  struct timeval end {};

  gettimeofday(&start, nullptr);

  for (unsigned long long p = 2; p * p < n; p++) {
    if (table[p] == true) {
      for (unsigned long long i = p * p; i < n; i += p) table[i] = false;
    }
  }
  gettimeofday(&end, nullptr);

  printf("printPrimesLessThanN1: %0.8f sec\n", time_diff(&start, &end));
}

void printPrimesLessThanN2(unsigned long long n) {
  vector<char> table(n, 1);
  struct timeval start {};
  struct timeval end {};

  gettimeofday(&start, nullptr);

  for (unsigned long long p = 2; p * p < n; p++) {
    if (table[p] == 1) {
      for (unsigned long long i = p * p; i < n; i += p) table[i] = 0;
    }
  }
  gettimeofday(&end, nullptr);

  printf("printPrimesLessThanN2: %0.8f sec\n", time_diff(&start, &end));
}

int main() {
  unsigned long long integer;

  while (true) {
    cout << "Enter integer: ";
    if (cin >> integer) {
      break;
    } else {
      cout << "Enter a valid integer value!\n";
      cin.clear();
      cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }
  }

  printPrimesLessThanN(integer);
  printPrimesLessThanN2(integer);

  return EXIT_SUCCESS;
}

Producción :

Enter integer: 1000000000
printPrimesLessThanN1: 47.39665985 sec
printPrimesLessThanN2: 10.11181545 sec