Aufgaben
Primzahlzwillinge und Primzahldrilling

  1. Ein Primzahlzwilling besteht aus zwei Primzahlen, deren Differenz zwei ist z.B. (5,7). Gib alle Primzahlzwillinge zwischen 1 und 100 an.
    
  2. Primzahldrillinge werden entsprechend den Primzahlzwillingen festgelegt, z. B. (3,5,7). Gib alle Primzahldrillinge zwischen 0 und 100 an.

Für diese Aufgabe benötigst Du folgendes Grundwissen: Primzahlen

  1. (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (71,73)
  2. (3,5,7)
Ermittle nach dem Sieb des Eratosthenes alle Primzahlen der Liste von 22 bis 8080. Im folgenden Video werden beispielhaft die ersten Schritte des Verfahrens dafür gezeigt. Ergänze die weiteren Verfahrensschritte, die nicht im Video gezeigt werden, bis du alle Primzahlen der Liste bestimmt hast. Andernfalls kannst du sofort damit beginnen, die vollständige Liste nach dem Verfahren zu bearbeiten.

Für diese Aufgabe benötigst Du folgendes Grundwissen: Sieb des Eratosthenes

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,\;3,\;5,\;7,\;11,\;13,\;17,\;19,\;23,\;29,\;31,\;37,\;41,\;43,\;47,\;53,\;59,\;61,\;67,\;71,\;73 und 7979.
sieb des eratosthenes

Wieso ist 1 keine Primzahl?

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:

$$\begin{align} 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{align}$$

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

Beim Ermitteln der Primzahlen nach dem Sieb des Eratosthenes lässt sich folgendes feststellen: Die Verfahrensschritte müssen in einer Liste {2,,N}\{2, \dots, N\} nur für alle Primzahlen pp mit pNp\leq \sqrt{N} angewendet werden. Wenn man eine Primzahl qq mit q>Nq > \sqrt{N} betrachtet, müssen keine Vielfachen von qq in der Liste durchgestrichen werden.
Erkläre diesen Zusammenhang!

Für diese Aufgabe benötigst Du folgendes Grundwissen: Primfaktorzerlegung

Beispiel

Mache dir den Zusammenhang zuerst an einem Beispiel klar. Betrachte dafür das Sieb des Eratosthenes für die Zahlen {2,,30}\{2, \dots, 30\}.
In dieser Tabelle wurden die Verfahrensschritte für die Primzahlen 2,32, 3 und 55 bereits durchgeführt. Nun ist 7>305,487 > \sqrt{30}\approx 5,48, das heißt alle Verfahrensschritte für Primzahlen p<30p < \sqrt{30} 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=2714=2\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 die Verfahrensschritte für Primzahlen pNp \leq \sqrt{N} bereits durchgeführt wurden. Wir wollen zeigen, dass wir keine Zahlen mehr durchstreichen müssen, wenn wir den Schritt für eine Primzahl q>Nq > \sqrt{N} durchführen.
Wenn wir eine Zahl nicht durchstreichen müssen, heißt dass, dass sie entweder selbst eine Primzahl ist, oder dass sie bereits durchgestrichen wurde. Wir wollen also zeigen: Wenn N<kN\sqrt{N} < k \leq N und kk keine Primzahl ist, wurde kk bereits durchgestrichen.
Wenn kk keine Primzahl ist, so können wir sie in ein Produkt k=rsk = r\cdot s zerlegen, sodass rr und ss beide nicht 11 sind. Wären rr und ss größer als N\sqrt{N}, so müsste k=rs>NN=Nk = r\cdot s > \sqrt{N}\cdot \sqrt{N} = N gelten. Dies kann nicht stimmen, weil wir kNk\leq N gewählt haben.
Also ist rNr \leq \sqrt{N} oder sNs\leq \sqrt{N} und kk wurde bereits durchgestrichen, als diese Zahl betrachtet wurde.
Kommentieren Kommentare