Wie Programmiert man Sieb des Eratosthenes in c++ ohne Schleifen?

Ein Anwender wird zu Beginn des Programms gefragt, bis zu welcher Zahl n er alle Primzahlen ausgegeben haben

möchte.

Nach der Abfrage gibt ein Anwender zum Beispiel eine 8 ein. Also ist n = 8

Die Ausgabe des Programms umfasst die Anzahl der gefundenen Primzahlen und die Primzahlen selbst. Eine

Ausgabe bei n = 8 sollte wie folgt aussehen:

Es wurden folgende Primzahlen bis zur Zahl 8 gefunden:

2, 3, 5, 7

Zur Bestimmung der Primzahlen muss das Sieb des Eratosthenes verwendet werden. Verwenden Sie Arrays, Modulo,

Rekursion und Funktionen, um das Sieb des Eratosthenes zu implementieren. Die Verwendung von Schleifen ist

untersagt.

Optionale Zusatzaufgabe

Geben Sie zusätzlich die Anzahl der gefunden Primzahlen aus. Beispiel:

Es wurden 4 Primzahlen gefunden.

Ich freue mich auf eure Hilfe.

Answer 1

[regex9]

Die Aufgabenstellung verrät es schon: Mit Rekursion. Das heißt, es gibt eine Funktion, die sich selbst immer wieder aufruft.

Ein Beispiel:

void count(int start, int end) {
  if (start > end) {
    return;
  }

  std::cout << start << std::endl;
  count(++start, end);
}

int main() {
  count(0, 5);
  return 0;
}   

Die Ausgabe wäre 0-5.

Nun vergleiche diesen Code einmal mit dem, bei dem eine Schleife stattdessen eingesetzt wird:

int start = 0;
int end = 5;

while (start <= end) {
  std::cout << start << std::endl;
  ++start;
}

Du findest dieselben Bestandteile.

• Die Hauptaktion (Ausgabe via std::cout)
• Eine Abbruchbedingung (Prüfung, ob start > end)
• Eine Zustandsänderung (++start), die dafür sorgt, dass je Wiederholung ein anderes Ergebnis ermittelt wird

Der Unterschied liegt darin, dass die rekursive Lösung mit dem Funktionsaufruf ihre nächste Wiederholung selbst ankurbeln muss. Damit diese über den aktuellen Zustand der Variablen Bescheid weiß, werden ihr die jeweiligen Werte als Argumente mitgegeben.

Du kannst die Aufgabe also zuerst mit Schleifen lösen und anschließend schauen, wie du den Lösungsweg zu einen rekursiven Algorithmus umwandelst.

Bezüglich des Sieb des Eratosthenes hilft der Wikipedia-Artikel.