Aufgaben zu Primzahlen

1. (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (71,73)

2. (3,5,7)

Führst du das Verfahren weiter aus, so ist die nächste Primzahl die $7$. Dementsprechend streichst du alle Vielfachen der 7. Erstaunlicherweise kannst du das Verfahren nach diesem Schritt bereits beenden. Die restlichen nicht-durchgestrichenen Zahlen sind Primzahlen. Alle Primzahlen von $2$ bis $80$ sind somit: $2,\;3,\;5,\;7,\;11,\;13,\;17,\;19,\;23,\;29,\;31,\;37,\;41,\;43,\;47,\;53,\;59,\;61,\;67,\;71,\;73$ und $79$.

Wenn $1$ eine Primzahl wäre, so wäre die Primfaktorzerlegung nicht eindeutig. Dies liegt daran, dass jede Zahl als Produkt von $1$ mit sich selbst geschrieben werden kann. Für die Zahl $6$ wären dann folgende Produkte Primfaktorzerlegungen:

$\def\arraystretch{1.25} \begin{aligned}6 & = 2\cdot 3 \\& = 2\cdot 3\cdot 1 \\& = 2\cdot 3\cdot 1\cdot 1 \\& = 2\cdot 3\cdot 1\cdot 1\cdot 1 \\& = \ldots\end{aligned}$

Da dies nicht sinnvoll ist, hat man festgelegt, dass $1$ keine Primzahl ist.

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.