sofatutor 30 Tage
kostenlos ausprobieren

Videos & Übungen für alle Fächer & Klassenstufen

Sieb des Eratosthenes 03:36 min

Textversion des Videos

Transkript Sieb des Eratosthenes

Hallo. Wenn Du weißt, was Primzahlen sind, dann können wir uns mal das Sieb des Eratosthenes ansehen. Das Sieb des Eratosthenes funktioniert so, dass man alle natürlichen Zahlen in ein Sieb kippt, also in der Vorstellung, und nur die Primzahlen bleiben im Sieb übrig und alle anderen natürlichen Zahlen fallen durch. Der Herr Eratosthenes lebte circa 300 vor Christus und hat dieses Verfahren übrigens nicht erfunden, sondern er war wohl der erste, der dieses Verfahren mit einem Sieb in Verbindung gebracht hat. Also wie funktioniert das? Wir haben hier die Zahlen von eins bis 100. Man kann natürlich auch mehr Zahlen nehmen oder weniger, das ist egal. Und wir können jetzt hier alle Zahlen rausschmeißen, die keine Primzahlen sind. Die Fallen also dann alle durchs Sieb. Eins ist schon mal keine Primzahl, die fliegt raus. Zwei ist eine Primzahl, die darf bleiben. Vielfache von zwei dürfen nicht bleiben, weil es keine Primzahlen sind. Denn die vier ist ja durch zwei teilbar, als Vielfaches von zwei, deshalb muss die vier raus, sechs ist ja drei mal zwei, deshalb durch zwei teilbar, deshalb muss die auch raus. Ebenso wie die acht, die zehn, die zwölf. 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98 und die 100. Die drei ist eine Primzahl und darf bleiben. Alle Vielfachen von 3, die jetzt hier noch zu sehen sind, sind keine Primzahlen, wie zum Beispiel die neun, die neun ist ja drei mal drei, deshalb ist die neun durch drei teilbar, also schon mal keine Primzahl. Die 15 ist fünf mal drei, deshalb keine Primzahl und muss auch raus. Ebenso wie die 21, die 27, die 33, 39 und die 45, die 51, die 57, 63, 69, 75, 81, 87, die 93 und die 99. Dann haben wir hier jetzt die fünf. Fünf ist eine Primzahl, alle Vielfachen von fünf sind keine Primzahlen. Da haben wir die 25, die muss raus, die 35, die 65, die 55 und noch die 85 und die 95. Die sieben ist eine Primzahl, alle Vielfachen von sieben sind keine Primzahlen, da haben wir noch die 49 und die 77. So, und Du siehst, es sind nur noch gelbe Bälle da, das sind also die Primzahlen von eins bis 100 und damit hat das Sieb funktioniert. Wir sind hier fertig. So, das wars zum Sieb des Eratosthenes. Viel Spaß damit, Tschüss.

40 Kommentare
  1. 😀 kurz aber gut erklärt

    Von Margit Saintandre, vor 11 Monaten
  2. Cool gemacht

    Von Margit Saintandre, vor 11 Monaten
  3. sehr gut

    Von david r., vor mehr als einem Jahr
  4. toll gut erklärt

    Von Bassam H., vor fast 2 Jahren
  5. Gute Erklärung, konnte es mir gut wegen dem Bälle Beispiel merken.

    Von Tomas Z., vor etwa 2 Jahren
Mehr Kommentare

Sieb des Eratosthenes Übung

Du möchtest dein gelerntes Wissen anwenden? Mit den Aufgaben zum Video Sieb des Eratosthenes kannst du es wiederholen und üben.

  • Finde mit Hilfe des Siebs von Eratosthenes alle Primzahlen von $1$ bis $25$.

    Tipps

    Markiere alle Vielfachen von $2$. Das sind $4$, $6$, $8$ und so weiter.

    Markiere alle Vielfachen von $3$, die noch nicht markiert wurden: $9$, $15$ und so weiter. Übrigens: Die $6$ ist ein Vielfaches von $2$ und wurde deswegen schon im vorherigen Schritt markiert.

    Fahre fort, bis du alle Vielfachen der Zahl $5$ markiert hast.

    Die Zahlen $2$, $3$ und $5$ sind Primzahlen und werden selbst nicht markiert, sondern nur deren Vielfache!

    Lösung

    Beim Sieb des Eratosthenes werden alle Zahlen, die keine Primzahlen sind, herausgestrichen oder markiert. Alle übrigen Zahlen sind Primzahlen.

    Gehe unabhängig von der Größe des Rasters immer so vor:

    • $1$ ist keine Primzahl und wird deswegen markiert.
    • $2$ ist eine Primzahl. Alle Vielfachen der Zahl $2$ können keine Primzahlen sein, weil sie mindestens noch $2$ als Teiler haben. Sie werden markiert. Hier sind das: $4$, $6$, $8$, $10$, $12$, $14$, $16$, $18$, $20$, $22$ und $24$.
    • $3$ ist eine Primzahl. Alle Vielfachen der Zahl $3$ sind ebenfalls keine Primzahlen. Markiere alle Vielfachen von $3$, die noch nicht markiert worden sind. Hier sind das: $9$, $15$ und $21$. Übrigens: Die Zahlen $6$, $12$, $18$ und $24$ wurden bereits im vorherigen Schritt als Vielfache von $2$ markiert.
    • $4$ ist keine Primzahl, sie ist schon als Vielfaches von $2$ markiert worden. Alle Vielfachen von $4$ sind ebenfalls keine Primzahlen, aber auch bereits alle als Vielfache von $2$ markiert worden.
    • $5$ ist wieder eine Primzahl. Alle Vielfachen der Zahl $5$ sind wieder keine Primzahlen. Hier ist das einzige Vielfache, das vorher noch nicht markiert worden ist, die Zahl $25$.
    Achtung: Die Zahlen, deren Vielfache wir herausstreichen, sind Primzahlen und werden selbst nicht herausgestrichen!

    Somit bleiben hier die Zahlen $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$ und $23$ übrig. Das Verfahren hat uns alle Primzahlen von $1$ bis $25$ herausgesiebt.

    Übrigens: Es reicht, wenn du bis zu der Zahl prüfst, die mit sich selbst multipliziert größer oder gleich der höchsten Zahl im Raster ist. Hier also bis zur Zahl $5$, denn $5 \cdot 5$ ergibt $25$, die höchste Zahl im Raster.

  • Erkläre, wie das Sieb des Eratosthenes funktioniert.

    Tipps

    Die Vielfachen einer Zahl können keine Primzahlen sein.

    Lösung

    Beim Sieb des Eratosthenes suchst du die Primzahlen in einem Bereich zwischen $1$ und einer Zahl, die du vorher festgelegt hast. Genau genommen findest du die Primzahlen, indem du alle Zahlen, die keine Primzahlen sind, ausschließt.

    Das Vorgehen funktioniert immer gleich, hat aber ein paar Besonderheiten:

    • Die Zahl $1$ ist keine Primzahl, da sie nur einen Teiler hat. Eine Primzahl hat allerdings genau zwei Teiler.
    • Immer die kleinste, nicht gestrichene Zahl ist eine Primzahl, denn sie ist durch keine andere Zahl außer $1$ und sich selbst teilbar, sonst wäre sie bereits gestrichen worden. Ihre Vielfachen sind wiederum keine Primzahlen und können gestrichen werden.
    • Wir sind fertig, wenn wir bei einer Zahl angekommen sind, die mit sich selbst multipliziert größer oder gleich der höchsten Zahl im Raster ist. Würden wir die Vielfachen einer noch größeren Zahl untersuchen, würden diese auch aus dem Raster heraus fallen.

  • Entscheide, welche der Zahlen Primzahlen sind.

    Tipps

    An der letzten Ziffer einer Zahl erkennt man sehr leicht, ob die Zahl durch $2$ oder $5$ teilbar ist.

    Du kannst das Sieb des Eratosthenes auch für Zahlen anwenden, die größer sind als $100$!

    Überlege: Können Vielfache überhaupt Primzahlen sein? Welche Teiler haben sie dann?

    Lösung
    • Die Zahl $144=12\cdot 12$ ist ein Vielfaches der Zahl $12$. Vielfache von Zahlen sind selbst keine Primzahlen, da sie mindestens einen Teiler haben, der nicht $1$ oder sie selbst ist, nämlich auf jeden Fall die Zahl. Also ist $144$ keine Primzahl.
    • Die Zahl $151$ ist eine Primzahl, wie du beispielsweise anhand des Sieb des Eratosthenes sehen kannst.
    • Die Zahl $152$ ist gerade und damit durch $2$ teilbar, also keine Primzahl.
    • Die Zahl $135$ ist durch $5$ teilbar und damit keine Primzahl!
    • Es gibt eine Reihe von Teilbarkeitsregeln, mit deren Hilfe man sehr schnell erkennen kann, ob eine Zahl eine bestimmte Zahl als Teiler besitzt oder nicht. Beispielsweise sind Zahlen mit letzter Ziffer $0, 2, 4, 6$ oder $8$ auf jeden Fall durch $2$ teilbar und damit keine Primzahlen (außer der $2$ selbst). Zahlen, deren letzte Ziffer eine $0$ oder $5$ ist, sind durch $5$ teilbar und damit keine Primzahlen (außer der $5$). Somit können wir diese Zahlen alle ausschließen. Genauer untersuchen müssen wir also die Zahlen, die auf $1,3,7$ oder $9$ enden.
  • Erkläre, warum man mit dem Sieb des Eratosthenes Primzahlen bestimmen kann.

    Tipps

    Man markiert alle Vielfachen der kleinsten, nicht gestrichenen Zahl.

    Die kleinste, nicht gestrichene Zahl ist jeweils immer eine Primzahl. Warum?

    Lösung

    Beim Sieb des Eratosthenes suchst du die Primzahlen in einem Bereich zwischen $1$ und einer Zahl, die du vorher festgelegt hast. Genau genommen findest du die Primzahlen, indem du alle Zahlen, die keine Primzahlen sind, ausschließt.

    Die kleinste, nicht gestrichene Zahl kommt nicht als Vielfaches einer anderen, kleineren Zahl vor und ist deshalb eine Primzahl. Wäre sie ein Vielfaches, dann wäre sie bereits im vorherigen Schritt gestrichen worden. Deswegen beginnt man auch immer bei der $1$ und arbeitet sich von klein nach groß vor.

    Alle gestrichenen Zahlen sind Vielfache von bestimmten Zahlen und deswegen keine Primzahlen, denn sie haben ja noch weitere Teiler außer der $1$ und sich selbst.

    Du musst immer nur bis zu der Zahl prüfen, die mit sich selbst multipliziert gleich oder größer der höchsten Zahl im Raster ist. Warum das so ist? Nehmen wir mal das Raster von $1$ bis $25$. Wenn du hier alle Vielfachen von Zahlen größer als $5$ streichst, hast du diese schon an anderer Stelle gestrichen. Sehen wir uns zum Beispiel die Vielfachen von $7$ an: $7 \cdot 2$ hast du schon bei $2 \cdot 7$ gestrichen und $7 \cdot 3$ schon bei $3 \cdot 7$.

  • Fasse zusammen, was Primzahlen sind.

    Tipps

    Eine Primzahl hat genau zwei Teiler: $1$ und sich selbst.

    Erinnere dich: Beim Sieb des Eratosthenes werden alle Vielfachen einer Primzahl gestrichen, weil sie selbst keine Primzahlen sein können. Sie haben nämlich immer mindestens noch die Primzahl als weiteren Teiler neben der $1$ und sich selbst.

    Probiere einmal aus, verschiedene Paare aus Primzahlen zu addieren, wie zum Beispiel die $3$ und die $5$. Was stellst du fest?

    Lösung

    Primzahlen sind besondere natürliche Zahlen:

    • Es gibt nur eine gerade Primzahl, nämlich die $2$.
    • Eine Primzahl ist nur durch $1$ und sich selbst teilbar und hat somit genau zwei Teiler. Deswegen ist übrigens auch die $1$ keine Primzahl, denn sie hat nur einen einzigen Teiler.
    • Die Vielfachen einer Primzahl können niemals Primzahlen sein. Sie haben außer $1$ und sich selbst nämlich mindestens noch einen weiteren Teiler: die Primzahl!
    Wenn du Primzahlen addierst, kommt manchmal zwar eine Primzahl heraus, wie bei $2+3=5$. Das ist aber keinesfalls immer so: $3+5=8$ und damit ist die Summer zweier Primzahlen nicht immer eine Primzahl.

    Übrigens: Das Sieb des Eratosthenes lässt sich auch für Zahlen, die größer sind als $100$, anwenden. Zum Beispiel ist $101$ eine Primzahl, probier es aus!

  • Finde eine Primzahl, die alle Eigenschaften erfüllt.

    Tipps

    Schreibe dir zunächst alle einstelligen Primzahlen auf, also alle Primzahlen, die kleiner sind als 10.

    Welche Kombinationen lassen sich aus diesen Primzahlen bilden?

    Welche Kombinationen aus zwei einstelligen Primzahlen fallen durch das Sieb des Eratosthenes?

    Du kannst alle Zahlen, die auf $2$ oder $5$ enden streichen. Denn diese sind durch $2$ bzw. $5$ teilbar.

    Lösung

    Unser Code besteht aus zwei Ziffern, die beide Primzahlen sind. Deswegen überlegen wir uns zuerst, welche einstelligen Zahlen dafür überhaupt in Frage kommen.

    • Zuerst suchen wir also alle Primzahlen, die kleiner sind als $10$.
    • Mit Hilfe des Siebs des Eratosthenes sehen wir, dass das die Zahlen $2, 3, 5$ und $7$ sind.
    Da der Code aus zwei Primzahlen besteht, reicht es, wenn wir uns alle möglichen Kombinationen aus diesen Primzahlen anschauen.
    • Das sind die Zahlen $22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75$ und $77$.
    Aus dieser Liste müssen wir jetzt nach und nach alle Zahlen streichen, die keine Primzahlen sind.
    • Gerade Zahlen oder Zahlen, die mit einer $5$ enden, sind durch $2$ oder $5$ teilbar und können deswegen bereits gestrichen werden.
    • Übrig bleiben $23, 27, 33, 37, 53, 57, 73$ und $77$.
    • Die Zahlen $33$ und $77$ sind durch $11$ teilbar, fallen also raus.
    Weiter untersuchen müssen wir also noch $23, 27, 37, 53, 57$ und $73$.
    • Die Zahlen $27$ und $57$ fallen durch das Sieb des Eratosthenes, denn $27=3\cdot9$ und $57=3\cdot19$.
    • Die Zahlen $23, 37, 53$ und $73$ sind Primzahlen und damit haben wir alle möglichen Codes gefunden.