Algorithme du crible d'Eratosthène en C++

Cet article explique comment implémenter l’algorithme de tamis d’ératosthène en C++.

Implémenter l’algorithme Sieve of Eratosthenes à l’aide du conteneur std::vector en C++

Le tamis d’Eratosthène est l’un des tamis de nombres premiers, représentant des algorithmes relativement efficaces pour trouver des nombres premiers. Il existe plusieurs algorithmes adaptés à différentes plages de nombres premiers, et ils ont également des caractéristiques de performances contrastées.

Le tamis d’Eratosthène peut être considéré comme le plus simple à mettre en œuvre, et il est assez efficace sur des portées plus petites. Même si sa complexité de temps d’exécution est O(N loglogN), il fonctionne mieux sur des plages plus petites.

Cet article implémentera cet algorithme en utilisant la méthode la plus simple pour être adaptée à l’article d’introduction. L’algorithme prend la valeur entière et trouve tous les nombres premiers inférieurs ou égaux à l’entier donné.

Dans un premier temps, nous construisons un tableau de valeurs booléennes qui a la même taille que l’entier donné et initialisons chaque élément pour avoir une valeur true.

Ensuite, nous parcourons ce tableau d’éléments et stockons la valeur false si l’élément donné a un index composite. Nous accédons aux indices du tableau en calculant les multiples de nombres premiers consécutifs à partir du plus petit - 2 et nous arrêtons l’itération une fois que le carré du nombre premier donné est plus grand que l’entier d’entrée - n. Les étapes précédentes sont implémentées à l’aide des boucles for imbriquées dans la fonction printPrimesLessThanN.

Enfin, nous parcourons ce vecteur et imprimons les indices des éléments qui ont une valeur true stockée. Notez que cette dernière opération est gérée par la boucle for à la fin de la fonction printPrimesLessThanN. Nous fournissons également le code du pilote dans la fonction main pour accepter l’entier indiquant la limite supérieure de l’utilisateur et valider l’entrée jusqu’à ce qu’elle soit passée à la fonction 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;
}

Production:

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

L’extrait de code précédent est un exemple de travail qui peut être optimisé avec diverses méthodes telles que l’exploitation de la concurrence dans le programme, le découpage et le stockage du tableau en mémoire afin que l’accès aux données soit optimisé, ou à l’aide d’autres informations algorithmiques. Cependant, il existe une petite idée qui peut économiser des multiples de temps d’exécution pour cette implémentation sans apporter d’énormes changements, et c’est de stocker les valeurs true/false dans le vecteur de char.

Comme vous pouvez le constater en exécutant plusieurs tests sur des nombres plus grands, le type bool est bien moins performant que le type intégral comme char ou même int. L’exemple de code suivant montre le scénario de référence simple pour les deux versions de la fonction - printPrimesLessThanN et imprime le temps écoulé à la fin du programme.

#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;
}

Production:

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