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 $77$. 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 $22$ bis $8080$ sind somit: $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,732,\backslash ;3,\backslash ;5,\backslash ;7,\backslash ;11,\backslash ;13,\backslash ;17,\backslash ;19,\backslash ;23,\backslash ;29,\backslash ;31,\backslash ;37,\backslash ;41,\backslash ;43,\backslash ;47,\backslash ;53,\backslash ;59,\backslash ;61,\backslash ;67,\backslash ;71,\backslash ;73$ und $7979$.

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

Da dies nicht sinnvoll ist, hat man festgelegt, dass $11$ 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\}\backslash \{2,\; \backslash dots,\; 30\backslash \}$.

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

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

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

Erklärung für allgemeines $nn$

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

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