If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Sieb des Eratosthenes

Das Sieb des Eratosthenes erlaubt uns, eine Liste von Primzahlen zu generieren. Erstellt von Brit Cruise

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.

Video-Transkript

Ich möchte nun eine alte Methode zum Erzeugen einer Liste von Primzahlen bis zu einer bestimmten Grenze N vorstellen, genannt das Sieb des Eratosthenes. Eratosthenes wurde 276 v. Chr. geboren. Also ist diese Methode über 2200 Jahre alt. Aber sie ist sehr einfach und elegant und man kann sie jedem Kind beibringen. Nehmen wir zum Beispiel an, wir wollen alle Primzahlen bis 100 berechnen, würde das genauso funktionieren, wenn wir bis zu 10.000 oder einer Milliarde berechnen wollten. So geht es: Nehmen wir an, alle Zahlen sind ungekennzeichnet, grau ist ungekennzeichnet. Wir beginnen am Anfang und wenn wir eine Zahl finden, die nicht markiert ist, wissen wir, dass sie Primzahl ist. Also treffen wir auf die zwei und sagen, zwei ist eine Primzahl, weil sie nicht markiert ist. Und dann können wir in der zweiten Phase alle Vielfachen von zwei eliminieren, weil wir wissen, dass sie zusammengesetzt sind. Also bam, wir springen weiter und eliminieren alle Vielfachen von zwei, rot bedeutet zusammengesetzt. Und jetzt wiederholen wir das. Wir gehen von zwei zu drei. Die Drei ist nicht markiert, also markieren wir drei als Primzahl. Und jetzt können wir alle Vielfachen von drei eliminieren. Eine wirklich einfache Optimierung ist, dass die Sechs schon durchgestrichen ist, wir streichen tatsächlich die Vielfachen anfangend bei der Quadratzahl dieser Zahl durch. Also drei mal drei ist neun. Wir beginnen bei neun und markieren alle Vielfachen von drei als zusammengesetzt. Und dann gehen wir zurück, wir springen weiter zu vier. Nun, die Vier ist markiert, wir wissen, dass es zusammengesetzt ist. Wir springen weiter zu fünf, wir finden eine nicht markierte Zahl, Fünf ist eine Primzahl. Nun, fünf mal fünf ist 25, wir gehen zu 25. Wir streichen 25, 30, 35, 40, 45 und so weiter durch. Das sind zusammengesetzte Zahlen. Wir gehen weiter, bis wir auf sieben treffen, wir wissen, dass sieben eine Primzahl ist, weil es nicht markiert ist. Sieben mal sieben ist 49, wir markieren 49 und alle Vielfachen von sieben darüber als zusammengesetzt. Jetzt gehen wir weiter, bis wir auf 11 treffen, 11 ist Primzahl. Beachte jetzt, dass 11 mal 11 größer als 100 ist, also können wir an diesem Punkt aufhören. Wir hätten sogar bei 10 aufhören können, denn jetzt sind alle verbleibenden nicht markierten Zahlen, wie du siehst, Primzahlen. Und in einem Schwung können wir sie alle als Primzahlen markieren. Und das ist der gesamte Algorithmus, so einfach. Und um zu verallgemeinern, wie wir das machen, damit wir ein Programm schreiben können, um dieses Sieb durchzuführen, wenn wir alle Primzahlen bis zu einer Zahl N finden wollen, erstellen wir zuerst eine Hauptschleife. Also für alle Zahlen A, von zwei bis zur Quadratwurzel von N Beachte hier, dass wir aufhören, wenn wir 10 erreichen, ich habe es als 11 gezeigt, wir hören tatsächlich auf, weil wir alle Primzahlen gefunden haben. Also von zwei bis zur Quadratwurzel von N, gehen wir wie folgt vor: Wenn A nicht markiert ist, dann wissen wir, dass A prim ist und wenn wir eine Primzahl finden, markieren wir alle Vielfachen von A als zusammengesetzt und das ist es. Also, finden wir eine Primzahl, markieren die Vielfachen, gehen zurück zum Anfang, erhöhen A um eins. Wir sind bei zwei, dann gehen wir zu drei, dann gehen wir zu vier, fünf und so weiter, und wenn wir fertig sind, haben wir alle Primzahlen. Beachte hier, dass dies auch eine Schleife ist. Wir haben also eine Hauptschleife, wenn wir eine Primzahl finden. Dieses Markieren der Vielfachen ist ebenfalls eine Schleife. Es ist wichtig zu bemerken, dass wir hier eine verschachtelte Schleife haben, wir haben eine Schleife in einer Schleife. Hier ist ein Beispiel für diesen Algorithmus in Aktion, den ich unten in JavaScript geschrieben habe. Wenn ich 100 eingebe, sind hier alle Primzahlen unter 100. Und wenn ich 200 eingebe, sind hier alle Primzahlen unter 200. Und wenn ich 850 eingebe, sind hier alle Primzahlen unter 850. Und unten habe ich dieses Programm mit einer Aufnahme, die erklärt, wie ich es eingerichtet habe.