Sieb des Eratosthenes-Algorithmus in C++

In diesem Artikel wird erklärt, wie Sie den Sieve of Eratosthenes-Algorithmus in C++ implementieren.

Implementieren Sie den Sieve of Eratosthenes-Algorithmus mit dem Container std::vector in C++

Das Sieb des Eratosthenes ist eines der Primzahlensiebe, das relativ effiziente Algorithmen zum Auffinden von Primzahlen darstellt. Es gibt mehrere Algorithmen, die für verschiedene Primzahlenbereiche geeignet sind, und sie haben auch gegensätzliche Leistungsmerkmale.

Sieb von Eratosthenes kann als das am einfachsten zu implementierende Sieb angesehen werden, und es ist bei kleineren Reichweiten ziemlich effizient. Obwohl seine Laufzeitkomplexität O(N loglogN) beträgt, schneidet es auf kleineren Entfernungen besser ab.

In diesem Artikel wird dieser Algorithmus mit der einfachsten Methode implementiert, die für den Einführungsartikel geeignet ist. Der Algorithmus nimmt den ganzzahligen Wert und findet alle Primzahlen kleiner oder gleich der gegebenen ganzen Zahl.

Zuerst konstruieren wir ein Array von booleschen Werten, das die gleiche Größe wie die gegebene ganze Zahl hat und initialisieren jedes Element mit einem true Wert.

Dann durchlaufen wir dieses Array von Elementen und speichern den false Wert, wenn das gegebene Element einen zusammengesetzten Index hat. Wir greifen auf die Array-Indizes zu, indem wir die Vielfachen aufeinanderfolgender Primzahlen berechnen, beginnend mit der kleinsten - 2, und wir stoppen die Iteration, sobald das Quadrat der gegebenen Primzahl größer ist als die eingegebene ganze Zahl - n. Die vorherigen Schritte werden mit den verschachtelten for-Schleifen in der Funktion printPrimesLessThanN realisiert.

Schließlich durchlaufen wir diesen Vektor und geben die Elementindizes aus, die einen true Wert gespeichert haben. Beachten Sie, dass letztere Operation von der for-Schleife am Ende der Funktion printPrimesLessThanN verarbeitet wird. Wir stellen auch Treibercode in der Funktion main bereit, um die ganze Zahl, die die obere Grenze des Benutzers angibt, zu akzeptieren und die Eingabe zu validieren, bis sie an die Funktion printPrimesLessThanN übergeben wird.

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

Ausgabe:

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

Das vorherige Code-Snippet ist ein funktionierendes Beispiel, das mit verschiedenen Methoden optimiert werden kann, z. Es gibt jedoch eine winzige Erkenntnis, die für diese Implementierung ein Vielfaches an Laufzeit sparen kann, ohne große Änderungen vorzunehmen, und zwar die Speicherung von true/false-Werten im Vektor von char s.

Wie Sie bei mehreren Tests mit größeren Zahlen feststellen können, schneidet der Typ bool deutlich schlechter ab als der ganzzahlige Typ wie char oder sogar int. Das folgende Codebeispiel zeigt das einfache Benchmark-Szenario für beide Versionen der Funktion - printPrimesLessThanN und druckt die verstrichene Zeit am Ende des Programms.

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

Ausgabe:

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