Dies ist eine alte Version des Dokuments!
Primzahlsuche: Zahlensieb
Vom griechischen Philosoph und Mathematiker Eratosthenes von Kyrene (3. Jahrhundert v. Chr.) ist ein Verfahren überliefert, Primzahlen bis zu einer beliebigen Grenze schnell zu finden. Das Verfahren ist bekannt als das "Sieb des Erathostenes" oder "Zahlensieb".
Idee
- Man stellt zunächst eine Liste mit allen Zahlen von 2 bis r gewünschten Obergrenze zusammen.
- Jetzt streicht man alle Vielfachen von 2, denn das sind ja keine Primzahlen (durch 2 teilbar) und "behält" die 2 als erste Primzahl.
- Die nächste nicht durchgestrichene Zahl ist die nächste Primzahl - die 3.
- Jetzt streicht man alle Vielfachen der 3.
- Jetzt wiederholt man die Schritte ab 3. bis man am Ende des Zahlenbereichs angekommen ist.
Die Zahlen, die dann noch übrig sind, sind die gesuchten Primzahlen.
Modellierung des Problems
Man verwendet ein Array aus booschen-Werten (wahr/falsch). "wahr" soll dabei für Primzahl stehen, "falsch" für "keine Primzahl". Wenn also das Arrayelement sieb[9] den Wert true hat, würde das bedeuten, dass wir 9 für eine Primzahl halten.
Aufgabe
Lade das BlueJ Projekt herunter oder klone dir das Repo und implementiere das Sieb des Eratosthenes.