Das Sieb des Eratosthenes

Das Sieb des Eratosthenes Übung

• Ergänze die ersten Schritte zur Bestimmung der Primzahlen mit Hilfe des Siebes von Eratosthenes.

  Tipps

  Eine Primzahl ist eine Zahl, die genau zwei Teiler hat.

  Schau dir die Vielfachenmenge der $5$ an: $\{5;10;15;20;25;...\}$.

  Die $5$ ist eine Primzahl. Alle folgenden Zahlen in der Vielfachenmenge können keine Primzahlen sein. Warum? Neben der $1$ und der Zahl selbst ist auch die $5$ ein Teiler. Die Zahl hat also mindestens drei Teiler.

  Lösung

  Mit dem Sieb von Eratosthenes kannst du alle Zahlen, die keine Primzahlen sind, aussieben:

  1. Schreibe zunächst die Zahlen auf. Du kannst dabei die $1$ weglassen, da diese keine Primzahl ist.
  2. Markiere die erste Zahl, nämlich die $2$. Diese ist die kleinste Primzahl. Streiche alle Vielfachen von der $2$ durch, da diese keine Primzahlen sein können. Sie sind nämlich durch $1$, sich selbst und mindestens noch durch $2$ teilbar.
  3. Markiere nun die nächste Zahl, nämlich die $3$. Auch diese ist eine Primzahl. Streiche nun alle Vielfachen der $3$ durch.
  4. Nun kannst du die nächste Zahl, die $5$ markieren. Das kleinste Vielfache der $5$, welches noch nicht durchgestrichen ist, ist die $25$. Da diese jedoch größer ist als $20$, bist du fertig.

  Nun kannst du die Primzahlen ablesen. Diese sind alle Zahlen, die noch nicht durchgestrichen sind: $2$; $3$; $5$; $7$; $11$; $13$; $17$ und $19$.

• Bestimme die Primzahlen bis $50$.

  Tipps

  Du musst bei jeder der gegebenen Zahlen die Teilbarkeit durch die Primzahlen $2$; $3$; $5$ sowie $7$ prüfen.

  Fünf der gegebenen Zahlen von $21$ bis $50$ sind Primzahlen.

  Lösung

  Hier siehst du das Sieb des Eratosthenes nach Streichen aller Zahlen, die keine Primzahlen sind. Die grünen Zahlen sind die gesuchten Primzahlen.

  Jede dieser Zahlen hat genau zwei Teiler: die $1$ und sich selbst.

• Entscheide, ob eine Primzahl vorliegt.

  Tipps

  Eine Primzahl hat genau zwei Teiler: die $1$ und sich selbst.

  Wenn du eine Zahl darauf untersuchen möchtest, ob sie eine Primzahl ist, genügt es, einen Teiler ungleich $1$ und der Zahl selbst zu finden.

  Hier siehst du einige Beispiele für die Endziffernregel:

  • Jede Zahl, die auf $0$; $2$; $4$; $6$ oder $8$ endet, ist durch $2$ teilbar.
  • Jede Zahl, deren letzten beiden Stellen durch $4$ teilbar sind, ist durch $4$ teilbar.
  • Jede Zahl, die auf $0$ oder $5$ endet, ist durch $5$ teilbar.
  • Jede Zahl, die auf $0$ endet, ist durch $10$ teilbar.

  Lösung

  Für jede Primzahl gilt: Sie hat genau zwei Teiler, nämlich die $1$ und sich selbst.

  Wenn du also zu einer gegebenen Zahl einen weiteren Teiler findest, kann diese Zahl keine Primzahl sein.

  • $111$: Bei dieser Zahl ist die Quersumme $1+1+1=3$ durch $3$ teilbar. Damit ist auch die Zahl durch $3$ teilbar. Es ist $111=3\cdot 37$. $111$ ist also keine Primzahl.
  • $222$ ist eine gerade Zahl, also durch $2$ teilbar. $222$ kann somit keine Primzahl sein.
  • $127$: Die Teilermenge dieser Zahl ist T$_{127}=\{1;127\}$. Damit ist $127$ eine Primzahl.
  • $135$ endet auf $5$ und ist somit durch $5$ teilbar und keine Primzahl.

• Bilde die Primfaktorzerlegung der Zahl $135$.

  Tipps

  Hier siehst du einige Beispiele für die Endziffernregel:

  • Jede Zahl, die auf $0$; $2$; $4$; $6$ oder $8$ endet, ist durch $2$ teilbar.
  • Ist die Quersumme einer Zahl durch $3$ teilbar, so ist auch die Zahl selbst durch $3$ teilbar.
  • Jede Zahl, die auf $0$ oder $5$ endet, ist durch $5$ teilbar.

  Schau dir ein Beispiel für eine Primfaktorzerlegung an. Die Zahl $12$ soll in Primfaktoren zerlegt werden.

  • $12=2\cdot 6$: Die $6$ ist keine Primzahl, kann also noch weiter zerlegt werden.
  • $6=2\cdot 3$: Beide Faktoren sind Primzahlen.

  Die Primfaktorzerlegung der $12$ ist fertig: $12=2\cdot 2\cdot 3$.

  Lösung

  Eine sehr wichtige Anwendung von Primzahlen ist die Primfaktorzerlegung. Diese benötigst du zum Beispiel zur Bestimmung des größten gemeinsamen Teilers oder der kleinsten gemeinsamen Vielfachen zweier oder mehrerer Zahlen.

  Bei einer Primfaktorzerlegung schreibst du eine natürliche Zahl als Produkt. Dabei sind alle Faktoren Primzahlen. Es ist durchaus möglich, dass eine Primzahl mehrmals als Faktor vorkommt.

  Um eine Primfaktorzerlegung durchzuführen, verwendest du Teilbarkeitsregeln. Hier siehst du einige:

  • Jede gerade Zahl, also eine Zahl, die auf $0$ oder $2$ oder $4$ oder $6$ oder $8$ endet, ist durch $2$ teilbar.
  • Ist die Quersumme einer Zahl durch $3$ teilbar, so ist auch die Zahl selbst durch $3$ teilbar.
  • Jede Zahl, deren letzten beiden Stellen durch $4$ teilbar sind, ist durch $4$ teilbar.
  • Jede Zahl, die auf $0$ oder $5$ endet, ist durch $5$ teilbar.

  Es gibt noch weitere Teilbarkeitsregeln. Für die Primfaktorzerlegung der Zahl $135$ genügen die Teilbarkeitsregeln für die Teilbarkeit durch $5$ sowie durch $3$.

  • Du siehst, die $135$ endet auf $5$, ist also durch $5$ teilbar. Rechne nun $135:5=27$.
  • Die Quersumme von $27$ ist $2+7=9$. Da diese durch $3$ teilbar ist, ist auch $27$ durch $3$ teilbar. Rechne wieder $27:3=9$.
  • Die $9$ ist keine Primzahl. Es gilt: $9=3\cdot 3$. Beide Faktoren sind Primzahlen.

  Nun bist du fertig: $135=3\cdot 3\cdot 3\cdot 5$.

  Die $135$ hat also die beiden Primzahlen $3$ und $5$ als Primfaktoren. Die $3$ kommt dreimal als Faktor vor.

• Beschreibe die Eigenschaften einer Primzahl.

  Tipps

  Schau dir Beispiele für Primzahlen an: $5$; $7$; $11$; $13$; ...

  Jede Zahl ist auf jeden Fall durch die $1$ und durch sich selbst teilbar.

  Überlege dir, ob du eine ungerade Zahl kennst, die keine Primzahl ist.

  Schau dir zum Beispiel die Vielfachen von $3$ an.

  Lösung

  Was sind Primzahlen?

  Primzahlen sind Zahlen, die genau zwei Teiler haben: die Zahl $1$ und sich selbst.

  • Insbesondere folgt damit, dass die $1$ keine Primzahl ist, da sie nur einen Teiler hat.
  • Die Zahl $2$ ist eine Primzahl. Diese ist die kleinste Primzahl und darüber hinaus die einzige gerade Primzahl. Wieso das so ist? Jede gerade Zahl ist durch die $2$ teilbar und hat damit neben der $1$ und sich selbst mindestens noch die $2$ als weiteren Teiler:
  • Es ist jedoch nicht jede ungerade Zahl eine Primzahl. Zum Beispiel ist die Teilermenge von $15$ gegeben durch $T_{15}=\{1;3;5;15\}$.

• Prüfe, ob eine Primzahl vorliegt.

  Tipps

  Streiche zunächst alle Vielfachen von $2$.

  Die $2$ ist die kleinste und übrigens die einzige gerade Primzahl.

  Streiche dann alle Vielfachen von $3$. Diese erkennst du daran, dass die Quersumme durch $3$ teilbar ist.

  Du musst die Teilbarkeit bis zur Zahl $7$ prüfen.

  Lösung

  Beim Sieb des Eratosthenes gehst du wie folgt vor:

  • Du streichst alle Vielfachen von bereits bekannten Primzahlen.
  • Die Vielfachen von $2$ sind alle geraden Zahlen. Du kannst also die Zahlen $56$; $58$; $60$; $62$ und $64$ streichen.
  • Streiche nun die Vielfachen von $3$, welche noch nicht gestrichen sind. Diese sind: $57$ und $63$.
  • Streiche die Vielfachen von $5$. Diese erkennst du an der Endziffer $0$ oder $5$. Die Vielfachen mit der Endziffer $0$, also die $60$ ist bereits gestrichen. Du musst also noch die $55$ streichen.
  • Streiche die Vielfachen von $7$. Hier kommen nur die $56$ sowie $63$ in Frage. Beide sind bereits gestrichen.
  • Die Vielfachen von $9$ sind ebenfalls schon gestrichen.

  Die Zahlen, welche noch nicht gestrichen sind, sind die gesuchten Primzahlen, also die $59$ sowie die $61$.