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 das Sieb des Eratosthenes implementiert, um alle Primzahlen zu finden, die kleiner oder gleich einer gegebenen Zahl sind.
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, schreibst du zuerst alle Zahlen von 2 bis einschließlich deiner gegebenen Zahl auf.
Dann gehst du so vor:
- Finde die nächste unmarkierte Zahl (überspringe dabei die markierten Zahlen).
Das ist eine Primzahl.
- Markiere alle Vielfachen dieser Primzahl als nicht prim.
Wiederhole diese Schritte, bis du jede Zahl durchgegangen bist.
Am Ende sind alle unmarkierten Zahlen Primzahlen.
Das Sieb des Eratosthenes streicht die Vielfachen jeder Primzahl mithilfe von Addition (wiederholtes Addieren der Primzahl) oder Multiplikation (direktes Berechnen ihrer Vielfachen) durch, statt jede Zahl auf Teilbarkeit zu prüfen.
Die Tests prüfen nicht, ob du den Algorithmus implementiert hast, sondern nur, ob du die richtigen Primzahlen gefunden hast.
Beispiel
Angenommen, 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 3 4 5 6 7 8 9 10
-
2 ist unmarkiert und daher eine Primzahl.
Markiere 4, 6, 8 und 10 als „nicht prim“.
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
3 ist unmarkiert und daher eine Primzahl.
Markiere 6 und 9 als nicht prim (das Markieren von 6 ist optional, denn sie ist bereits markiert).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
4 ist als „nicht prim“ markiert, also überspringen wir sie.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
5 ist unmarkiert und daher eine Primzahl.
Markiere 10 als nicht prim (optional, denn sie ist bereits markiert).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
6 ist als „nicht prim“ markiert, also überspringen wir sie.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
7 ist unmarkiert und daher eine Primzahl.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
8 ist als „nicht prim“ markiert, also überspringen wir sie.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
9 ist als „nicht prim“ markiert, also überspringen wir sie.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
10 ist als „nicht prim“ markiert, also hören wir auf, da es keine weiteren Zahlen mehr zu prüfen gibt.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
Du hast alle Zahlen untersucht und festgestellt, dass 2, 3, 5 und 7 noch unmarkiert sind. Sie sind also die Primzahlen kleiner oder gleich 10.
