Einführung
Du hast auf einem Garagenflohmarkt eine große Kiste voller zufälliger Computerteile gekauft.
Jetzt hast du angefangen, die Teile zusammenzusetzen, um eigene Computer zu bauen.
Du willst die Leistung verschiedener Kombinationen von Teilen testen und beschließt, dein eigenes Benchmarking-Programm zu schreiben, um zu sehen, wie deine Computer abschneiden.
Du entscheidest dich für den berühmten „Sieve of Eratosthenes“, einen uralten Algorithmus, der deine Computer aber bis an ihre Grenzen treiben dürfte.
Anleitung
Deine Aufgabe ist es, ein Programm zu schreiben, das den Algorithmus des Siebs des Eratosthenes implementiert, um alle Primzahlen kleiner oder gleich einer gegebenen Zahl zu finden.
Eine Primzahl ist eine Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist.
Zum Beispiel sind 2, 3, 5, 7, 11 und 13 Primzahlen.
Im Gegensatz dazu ist 6 keine Primzahl, denn sie ist nicht nur durch 1 und sich selbst teilbar, sondern auch durch 2 und 3.
Um das Sieb des Eratosthenes zu verwenden, erstellst du zuerst eine Liste mit allen Zahlen zwischen 2 und deiner gegebenen Zahl.
Dann wiederholst du die folgenden Schritte:
- Finde die nächste nicht markierte Zahl in deiner Liste (überspringe dabei markierte Zahlen).
Sie ist eine Primzahl.
- Markiere alle Vielfachen dieser Primzahl als nicht prim.
Du wiederholst diese Schritte so lange, bis du jede Zahl in deiner Liste durchgegangen bist.
Am Ende sind alle nicht markierten Zahlen prim.
Die Tests prüfen nicht, ob du den Algorithmus implementiert hast, sondern nur, ob du die richtige Liste der Primzahlen gefunden hast.
Um zu prüfen, ob du das Sieb korrekt implementierst, ist ein guter erster Test zu prüfen, ob du keine Division oder Restwertoperationen verwendest.
Beispiel
Sagen wir, du suchst die Primzahlen kleiner oder gleich 10.
- Schreibe 2, 3, 4, 5, 6, 7, 8, 9, 10 auf und lass sie alle unmarkiert.
- 2 ist unmarkiert und daher eine Primzahl.
Markiere 4, 6, 8 und 10 als „nicht prim“.
- 3 ist unmarkiert und daher eine Primzahl.
Markiere 6 und 9 als nicht prim (6 zu markieren ist optional, da sie bereits markiert wurde).
- 4 ist als „nicht prim“ markiert, also überspringen wir sie.
- 5 ist unmarkiert und daher eine Primzahl.
Markiere 10 als nicht prim (optional, da sie bereits markiert wurde).
- 6 ist als „nicht prim“ markiert, also überspringen wir sie.
- 7 ist unmarkiert und daher eine Primzahl.
- 8 ist als „nicht prim“ markiert, also überspringen wir sie.
- 9 ist als „nicht prim“ markiert, also überspringen wir sie.
- 10 ist als „nicht prim“ markiert, also hören wir auf, da es keine weiteren Zahlen mehr zu prüfen gibt.
Du hast alle Zahlen geprüft und festgestellt, dass 2, 3, 5 und 7 noch unmarkiert sind.
Das heißt, sie sind die Primzahlen kleiner oder gleich 10.
