Was ist das Sieb des Eratosthenes?

Das nach von Kyrene (ca. 275 v. Chr. – ca. 194 v. Chr.) als Sieb des benannte Verfahren dient der der bis zu einer beliebigen Grenze. Das Verfahren war schon lange vor Eratosthenes bekannt. Der vielseitige Gelehrte prägte jedoch den Begriff Sieb.

Wie funktioniert das Sieb des Eratosthenes?

Das Verfahren funktioniert so, dass man aus dem betrachteten Zahlenbereich alle Zahlen streicht, die keine Primzahlen sein können.

Übrig bleiben die Primzahlen im Zahlenbereich.

Dabei nutzt man die Bedingung für Primzahlen aus, dass eine Primzahl nur durch 1 und durch sich selbst teilbar ist. Eine Primzahl ist somit kein Vielfaches einer anderen Zahl, denn sonst wäre diese andere Zahl ja auch ein Teiler.

Anleitung für das Sieb des Eratosthenes

Schreiben Sie also alle Zahlen im betrachteten Zahlenbereich auf. Eins ist nicht prim und kann gestrichen werden.

Nun nehmen Sie jeweils die nächste noch nicht gestrichene Zahl – sie ist eine Primzahl, weil sie kein Vielfaches einer anderen ist.

Streichen Sie alle ihre Vielfachen, da diese nicht prim sein können.

Dies wiederholen Sie so lange, bis der Zahlenbereich erschöpft ist.

Optimierung des Sieb des Eratosthenes?

Zwei Beobachtungen beschleunigen das Verfahren deutlich:

  1. Mit den Streichungen der Vielfachen kann bei der Quadratzahl begonnen werden, da alle kleineren Vielfachen bereits durch vorhergehende Primzahlen abgedeckt sind.
  2. Die Streichungen selbst müssen nur bei Zahlen durchgeführt werden, die kleiner oder gleich der Wurzel der Zahl sind, die den Zahlenbereich begrenzt, da Primfaktoren einer zusammengesetzten Zahl immer kleiner oder gleich ihrer Wurzel sind.

Beispiel zum Sieb des Eratosthenes

Als beispielhafte Anwendung des Sieb des Eratosthenes bestimmen Sie mit ihm die Primzahlen bis 100.


Dies könnte Ihnen auch gefallen:

Dieser Beitrag wurde unter Mathematik abgelegt und mit , , verschlagwortet. Setze ein Lesezeichen auf den Permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>