Sieb des Erathostenes


Diese Seite Unterstützt den ScriptLoader

Das Sieb des Erathostenes "produziert" Primzahlen von 2 bis zu einer beliebigen Grenze.

 

Beim Algorithmus wird eine Zahl ungleich 0 als Primzahl angenommen (am Anfang die 2).

Anschließend werden alle Vielfachen dieser Zahl gestrichen (i.e. auf 0 gesetzt).

 

Im Fall 2 sind das alle geraden Zahlen (4, 6, 8, 10 usw.).

Die nachfolgende Zahl ist die 3, da diese nicht gestrichen wurde. Dies ist die neue Primzahl und alle weiteren Vielfachen der 3 werden getrichen. Die nächste (nicht gestrichene Zahl) ist dann die 5.

 

In einem Feld bis 100 ist die letzte Zahl bzw. dessen vielfaches, welches bearbeitet werden muss, die Zahl 9, danch kommt die 10 welche in allen ihren vielfachen durch die 2 schon ausgeschlossen wurde. Immer so weiter geht es mit der 11 und allen nachfolgenden Zahlen.

 

Interaction#2