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.

Das Grundgerüst eines BlueJ Projekts kannst du hier herunterladen oder mit dem Befehl git clone https://gitea.schule.social/QGM-Unterricht/bluej-eratosthenes.git]] aus dem Repo klonen. ===== 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.