Das „Sieb des Eratosthenes“ ist ein von dem griechischen Philosophen Eratosthenes (276-195 v. Chr.) entwickelter Algorithmus zur Berechnung aller Primzahlen bis zu einer vorgegebenen natürlichen Zahl n. Der Algorithmus in Umgangssprache (angelehnt an den „Duden der Informatik“):
1. Man schreibe alle Zahlen von 1 bis n hin und streiche die Zahl 1 durch.
2. Sei i die kleinste noch nicht durchgestrichene und nicht eingerahmte Zahl. Solange i existiert und i² ≤ n ist, rahme man i ein und streiche alle Vielfachen von i durch (die Vielfachen von i werden „ausgesiebt“).
3. Die eingerahmten und die nicht durchgestrichenen Zahlen sind die Primzahlen von 1 bis n.
1 a) Führen Sie den Algorithmus zunächst auf einem Blatt Papier für die Zahlen von 1 bis 25 durch.
Mein Ansatz:
alle Zahlen von 1 bis 25 hingeschrieben und die 1 durchgestrichen. Solange i existiert und i² ≤ n ist rahme man i ein.
ich hab das so verstanden, dass die Quadratzahl kleiner gleich 25 sein soll. diese soll man einrahmen.
Die Zahlen sind 2, 3, 4, 5.
Das mit dem vielfachen versteher ich nicht ganz und die anderen aufgaben kann ich auch nicht
Bitte um Hilfeee!
b) Welche Grundoperationen (elementare Algorithmen) lassen sich in obigem Algorithmus identifizieren?
c) Auf jeder Stufe des Algorithmenentwurfs sollte man sich Gedanken zur Optimierung machen. Wie lässt sich der Algorithmus bereits jetzt optimieren, noch bevor er als Pseudocode ausformuliert wird? Welche Datenstruktur kann für das Sieb benutzt werden?
d) Formulieren Sie den Algorithmus in Form von Pseudocode. Verwenden Sie dazu die Grundoperationen aus Aufgabe b)
