Algoritmo da peneira de Eratóstenes em C++

Este artigo irá explicar como implementar o algoritmo crivo de eratóstenes em C++.

Implementar o algoritmo Sieve de Eratóstenes usando o recipiente std::vector em C++

A peneira de Eratóstenes é uma das peneiras de números primos, representando algoritmos relativamente eficientes para encontrar primos. Existem vários algoritmos adequados para diferentes intervalos de números primos, e eles também têm características de desempenho contrastantes.

A peneira de Eratóstenes pode ser considerada a mais fácil de implementar e é bastante eficiente em intervalos menores. Mesmo que sua complexidade de tempo de execução seja O(N loglogN), ele tem um desempenho melhor em intervalos menores.

Este artigo implementará esse algoritmo usando o método mais direto adequado para o artigo introdutório. O algoritmo pega o valor inteiro e encontra todos os números primos menores ou iguais ao inteiro fornecido.

Em primeiro lugar, construímos um array de valores booleanos que tem o mesmo tamanho do inteiro dado e inicializamos cada elemento para ter um valor true.

Em seguida, iteramos por meio desse array de elementos e armazenamos o valor false se o elemento fornecido tiver um índice composto. Acessamos os índices do array calculando os múltiplos de primos consecutivos começando do menor - 2 e paramos a iteração quando o quadrado do primo fornecido é maior que o inteiro de entrada - n. As etapas anteriores são implementadas usando os loops for aninhados na função printPrimesLessThanN.

Finalmente, percorremos este vetor e imprimimos os índices dos elementos que possuem o valor true armazenado. Observe que a última operação é tratada pelo loop for no final da função printPrimesLessThanN. Também fornecemos o código do driver na função main para aceitar o número inteiro que denota o limite superior do usuário e validar a entrada até que seja passada para a função 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;
}

Produção:

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

O trecho de código anterior é um exemplo funcional que pode ser otimizado com vários métodos, como explorar a simultaneidade no programa, dividir e armazenar o array na memória para que o acesso aos dados seja otimizado ou usar outros insights algorítmicos. Embora, haja um pequeno insight que pode economizar múltiplos de tempo de execução para esta implementação sem fazer grandes mudanças, que é armazenar valores true/false no vetor de char.

Como você pode observar executando vários testes em números maiores, o tipo bool tem um desempenho muito pior do que o tipo integral como char ou mesmo int. O exemplo de código a seguir mostra o cenário de benchmark simples para ambas as versões da função - printPrimesLessThanN e imprime o tempo decorrido no final do 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;
}

Produção:

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