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".
Die Zahlen, die dann noch übrig sind, sind die gesuchten Primzahlen.
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.
Das Grundgerüst eines BlueJ Projekts kannst du hier herunterladen.
grenze
abdecken kannst.Ein König will zu seinem Geburtstag alle 100 Gefangenen, die in Einzelzellen (von 1 bis 100 durchnummeriert) sitzen, freilassen. Dazu schickt er einen Boten, der alle Türen aufschließen soll.
Während der Bote den Befehl ausführt, kommen dem König Bedenken. Er schickt einen zweiten Boten hinterher, der jede zweite Tür (d.h. die Türen 2, 4, 6, usw.) wieder schließt. Bei jedem "Schließvorgang" wird eine Türe entweder aufgeschlossen (wenn zu) oder zugeschlossen (wenn auf).
Danach schickt er einen dritten Boten, der jede dritte Türe (also 3, 6, 9, …) weiterschließt, usw. bis zum 100. Boten.
Welche Türen sind am Schluss offen? Erstelle ein Programm, das diese Frage beantwortet. Lässt sich das Ergebnis erklären?
Filename | Filesize | Last modified |
---|---|---|
arrays_02_eratosthenes.odp | 64.1 KiB | 25.03.2021 12:50 |
arrays_02_eratosthenes.pdf | 54.9 KiB | 25.03.2021 12:50 |