Beim Ermitteln der Primzahlen nach dem Sieb des Eratosthenes lässt sich folgendes feststellen: Die Verfahrensschritte müssen in einer Liste nur für alle Primzahlen mit angewendet werden. Denn die Vielfachen von Primzahlen mit sind bereits durchgestrichen.
Erkläre diesen Zusammenhang!
Lösung anzeigen
Beispiel
Mache dir den Zusammenhang zuerst an einem Beispiel klar. Betrachte dafür das Sieb des Eratosthenes für die Zahlen .
In dieser Tabelle wurden die Verfahrensschritte für die Primzahlen und bereits durchgeführt. Nun ist , das heißt alle Verfahrensschritte für Primzahlen wurden durchgeführt. Weiter ist jedes Vielfache von und in der Liste bereits durchgestrichen.
Betrachte zum Beispiel die Zahl . Diese ist ein Vielfaches von , denn . Aber sie wurde bereits durchgestrichen, als du die Vielfachen von durchgestrichen hast.
Somit kannst du alle weiteren Zahlen, die noch nicht durchgestrichen wurden, umkringeln, da diese Primzahlen sind.
Erklärung für allgemeines
Wir nehmen an, dass wir die Verfahrensschritte für Primzahlen bereits durchgeführt haben. Dann ist jede Zahl mit , die ein Vielfaches einer Primzahl mit ist, bereits durchgestrichen. Die Verfahrensschritte brauchen also für Primzahlen mit nicht durchgeführt werden.
Da ein Vielfaches von ist, lässt sich darstellen als mit . Damit ist aber . Denn wäre , dann wäre , im Widerspruch zur Voraussetzung, dass ist. Die zusammengesetzte Zahl ist also als Vielfaches von mit bereits durchgestrichen.