© Arndt Brünner   •  Matheseitenüberblick    •  Primzahlliste mit Eratosthenes   •  Primzahlen etc.   •  zurück

Das Primzahlsieb des Eratosthenes

Der griechische Mathematiker Eratosthenes (ca. 275 - 194 v.Chr.) beschrieb ein Verfahren, mit dem man in der Reihe der Natürlichen Zahlen alle Primzahlen "aussieben" kann.

Da Primzahlen nur durch 1 und sich selbst teilbar sind, sind sie auch kein Vielfaches von anderen Zahlen. Zahlen, die nicht prim sind, sind Vielfache einer oder mehrerer anderer (und kleinerer) Zahlen. Eratosthenes Verfahren beruht auf dieser Vorüberlegung.

Zur Ausführung streiche man in einer zusammenhängenden Liste von natürlichen Zahlen, die bei der 2 beginnt, alle "echten" Vielfachen der ersten Zahl, also von 2, d.h.: 4, 6, 8, 10, ... Sodann streiche man alle echten Vielfachen der 3 (6, 9, 12, 15, ...). Man fahre mit der nächsten noch stehenden Zahl (es ist die 5, da die 4 als Vielfaches von 2 bereits gestrichen wurde) analog fort und wiederhole den Vorgang, bis in der Liste keine Zahl mehr ein Vielfaches einer anderen ist. Dann sind die Primzahlen übrig geblieben.

Man kann auch bei höheren Zahlen beginnen und/oder unregelmäßig vorgehen, und wird dennoch am Ende alle Nichtprimzahlen gestrichen haben.

Wenn die Liste bis zu einer Zahl n geht und man von der kleinsten Zahl ab nach dem o.g. Verfahren vorgeht, so können alle noch verbliebenen Zahlen nur noch Vielfache in der Liste haben, die größer oder gleich ihres Quadrates sind, denn alle möglichen kleineren Teiler sind ja bereits gestrichen. Es genügt also, das Verfahren nur für diejenigen Zahlen m durchzuführen, für die m² ≤ n gilt.

Version: 28. 10. 2001, 0:04