Beispiel

Mache dir den Zusammenhang zuerst an einem Beispiel klar. Betrachte dafür das Sieb des Eratosthenes für die Zahlen $\{2, \dots, 30\}$.

In dieser Tabelle wurden die Verfahrensschritte für die Primzahlen $2, 3$ und $5$ bereits durchgeführt. Nun ist $7 > \sqrt{30}\approx 5{,}48$, das heißt alle Verfahrensschritte für Primzahlen $p < \sqrt{30}$ wurden durchgeführt. Weiter ist jedes Vielfache von $7, 11, 13, 17, 19, 23$ und $29$ in der Liste bereits durchgestrichen.

Betrachte zum Beispiel die Zahl $14$. Diese ist ein Vielfaches von $7$, denn $14=2\cdot 7$. Aber sie wurde bereits durchgestrichen, als du die Vielfachen von $2$ durchgestrichen hast.

Somit kannst du alle weiteren Zahlen, die noch nicht durchgestrichen wurden, umkringeln, da diese Primzahlen sind.

Erklärung für allgemeines $n$

Wir nehmen an, dass wir die Verfahrensschritte für Primzahlen $p \leq \sqrt{n}$ bereits durchgeführt haben. Dann ist jede Zahl $k$ mit $\sqrt n < k \le n$, die ein Vielfaches einer Primzahl $q$ mit $q > \sqrt n$ ist, bereits durchgestrichen. Die Verfahrensschritte brauchen also für Primzahlen $q$ mit $q > \sqrt n$ nicht durchgeführt werden.

Da $k$ ein Vielfaches von $q$ ist, lässt sich $k$ darstellen als $k = q \cdot r$ mit $r > 1$. Damit ist aber $r \le \sqrt n$. Denn wäre $r > \sqrt n$, dann wäre $k = q \cdot r > \sqrt n \cdot \sqrt n = n$, im Widerspruch zur Voraussetzung, dass $k \le n$ ist. Die zusammengesetzte Zahl $k$ ist also als Vielfaches von $r$ mit $r \le \sqrt n$ bereits durchgestrichen.