Rechner: Sieb des Eratosthenes

Um Primzahlen zu ermitteln, gibt es verschiedene Methoden. Eine der ersten Methoden hatte der Mathematiker Eratosthenes entwickelt, diese Methode heißt daher „Sieb des Eratosthenes“.

Bei diesem Verfahren werden alle Vielfachen (beginnend bei der Zahl 2) weggestrichen, da Vielfache keine Primzahlen sein können, denn sie haben mehr als zwei Teiler (also nicht nur 1 und sich selbst, so wie bei den Primzahlen gefordert).

Nachfolgendes animiertes Programm zeigt das Verfahren vom „Sieb des Eratosthenes“:

Hinweis: Wir beginnen mit den Vielfachen von 2 (also 2, 4, 6, 8, …), dann folgen die Vielfachen der Zahl 3 (also 3, 6, 9, … die 6 wurde bereits gestrichen, da 6 auch ein Vielfaches der Zahl 2 ist). Genau so verfährt das Programm oben: Sofern eine Zahl als Vielfaches weggestrichen ist, wird sie nicht mehr betrachtet.