Primzahlen – Sieb des Eratosthenes

Primzahlen – Sieb des Eratosthenes Übung

• Streiche die Vielfachen der nächsten Primzahl.

  Tipps

  Eine Zahl ist durch $3$ teilbar, wenn ihre Quersumme durch $3$ teilbar ist.

  Beispiel:

  • $45 ~\Rightarrow~$ Quersumme $= 4 + 5 = 9 ~\Rightarrow~$ durch $3$ teilbar
  • $49 ~\Rightarrow~$ Quersumme $= 4 + 9 = 13 ~\Rightarrow~$ nicht durch $3$ teilbar

  Es gibt $9$ ungerade echte Vielfache von $3$ unter den Zahlen bis $60$.

  Lösung

  Sind $57$ und $59$ Primzahlen? Um das herauszufinden, kannst du die Primfaktorzerlegung der Zahlen ausrechnen. Da auch große Primzahlen wie $29$ oder $31$ darin vorkommen können, ist die Primfaktorzerlegung nicht der einfachste Lösungsweg.

  Das Sieb des Eratosthenes hilft dir dabei, auf einfache Weise herauszufinden, ob $57$ und $59$ Primzahlen sind: Du markierst in der Liste der Zahlen von $1$ bis $50$ zuerst alle echten Vielfachen von $2$. In der Aufgabe ist das schon erledigt, denn alle geraden Zahlen $>2$ sind bereits orange markiert. Als Nächstes markierst du alle echten Vielfachen von $3$, dann die von $5$ und schließlich die von $7$. Diese Zahlen zu finden, ist nicht schwierig: Durch $3$ ist jede dritte Zahl teilbar, durch $5$ ist jede fünfte Zahl teilbar. Da die Vielfachen von $2$ bereits markiert sind, musst du nur noch die ungeraden Zahlen $>1$ beachten. Beginne also mit denjenigen ungeraden Zahlen, die Vielfache von $3$ sind, und markiere die Zahlen $9$, $15$, $21$, $27$, $33$, $39$, $45$, $51$ und $57$ gelb. Echte Vielfache von $5$, die nicht bereits durch $2$ oder $3$ teilbar sind, sind die Zahlen $25$, $35$ und $55$. Markiere sie blau. Die einzige Zahl bis $60$, die echt durch $7$ teilbar ist und keinen kleineren Primfaktor enthält, ist $49$. Markiere sie violett.

  Die Zahl $57$ ist gelb markiert, denn $57$ kommt in der $3$-er-Reihe vor. $57$ ist also keine Primzahl. Die Zahl $59$ bleibt in deiner Liste unmarkiert und ist daher eine Primzahl.

• Beschreibe das Sieb des Eratosthenes.

  Tipps

  Schreibe zuerst alle Zahlen von $1$ bis $100$ auf.

  Im letzten Schritt bleiben nur die Primzahlen übrig.

  Beginne die Streichung der teilbaren Zahlen mit der kleinsten Primzahl.

  Lösung

  Das Sieb des Eratosthenes ist ein Verfahren zum Auffinden von Primzahlen. Du streichst aus einer Liste von Zahlen nacheinander alle Vielfachen der Primzahlen. Um das Verfahren handhabbar zu machen, beginnst du mit der kleinsten Primzahl – also $2$ – und streichst zuerst alle geraden Zahlen. Die Liste enthält jetzt nur noch jede zweite Zahl, nämlich nur noch ungerade Zahlen. Im nächsten Schritt streichst du alle Zahlen, die durch $3$ teilbar sind. Das sind genau die ungeraden Zahlen mit durch $3$ teilbarer Quersumme. Als Nächstes streichst du von den verbleibenden Zahlen alle, die durch $5$ teilbar sind. Alle diese Zahlen haben als letzte Ziffer eine $5$ und haben eine Quersumme, die nicht durch $3$ teilbar ist (andernfalls sind sie bereits vorher gestrichen worden). Schließlich streichst du noch alle durch $7$ teilbaren Zahlen, die noch auf der Liste verblieben sind. Das sind alle Zahlen, deren kleinster Primfaktor $7$ ist. Denn alle Zahlen mit einem Primfaktor $<7$ hast du bereits vorher gestrichen und die kleinste Zahl, deren kleinster Primfaktor $11$ ist, ist die Zahl $11^2 = 121$, diese steht also gar nicht mehr auf deiner Liste.

  So erhältst du folgende Reihenfolge:

  1. Schreibe die Zahlen von $1$ bis $100$ auf.
  2. Streiche die Zahl $1$ und alle geraden Zahlen $>2$.
  3. Die Liste enthält jetzt nur noch halb so viele Zahlen wie am Anfang.
  4. Streiche aus den ungeraden Zahlen $>3$ alle, deren Quersummen durch $3$ teilbar sind.
  5. Streiche alle zweistelligen Zahlen mit der letzten Ziffer $5$.
  6. Streiche alle zweistelligen Zahlen, deren kleinster Primfaktor $7$ ist.
  7. Alle verbleibenden Zahlen sind Primzahlen

• Erschließe die Primfaktoren.

  Tipps

  Bei der Primfaktorzerlegung schreibst du eine Zahl als Produkt von Primzahlen. Die einzelnen Primzahlen können als Faktoren auch mehrfach vorkommen. So hat z. B. die Zahl $63$ die Primfaktorzerlegung:

  $63 = 3 \cdot 3 \cdot 7$.

  Dividiere die Zahlen durch ihre Primfaktoren, um weitere Primfaktoren zu finden.

  Eine Zahl ist genau dann durch $3$ teilbar, wenn die Summe ihrer Ziffern durch $3$ teilbar ist.

  Lösung

  Du kannst das Sieb des Eratosthenes nicht nur benutzen, um Primzahlen zu finden, sondern auch um die Primfaktorzerlegung einer Zahl auszurechnen. Beginne mit der kleinsten Primzahl, also $2$: Prüfe alle vorgegebenen Zahlen auf ihre Teilbarkeit durch $2$. Hier ist nur $68$ durch $2$ teilbar, die anderen Zahlen sind ungerade. Teile $68$ durch $2$ und erhalte $68:2=34$. Prüfe wieder auf die Teilbarkeit durch $2$ und dividiere: $34:2=17$. Die Zahl $17$ ist prim, daher lautet die Primfaktorzerlegung wie folgt:

  $68 = 2 \cdot 2 \cdot 17$

  Die nächstgrößere Primzahl ist $3$. Prüfe alle vorgegebenen Zahlen auf ihre Teilbarkeit durch $3$. Hier ist nur $87$ durch $3$ teilbar, denn $87$ ist die einzige der vorgegebenen Zahlen mit einer durch $3$ teilbaren Quersumme. Teile $87$ durch $3$ und erhalte $87:3=29$. Mit dem Sieb des Eratosthenes findest du leicht heraus, dass $29$ prim ist, denn $29$ ist weder durch $2$ noch durch $3$, $5$ oder $7$ teilbar. Für Zahlen bis $100$ genügt es, diese Primzahlen als Teiler zu testen. Die Primfaktorzerlegung ist demnach:

  $87 = 3 \cdot 29$

  Teilbarkeit durch die nächstgrößere Primzahl $5$ erkennst du an der letzten Ziffer: Nur die Zahl $65$ hat als letzte Ziffer eine $0$ oder $5$. Teile durch $5$ und erhalte $65:5=13$. Da $13$ weder durch $2$ noch durch $3$, $5$ oder $7$ teilbar ist, ist $13$ prim und du erhältst:

  $65=5 \cdot 13$

  Schließlich bleibt noch die Division durch $7$. Da die Primfaktorzerlegung eindeutig ist, ist keine der zuvor genannten Zahlen durch $7$ teilbar. Dividiere $217$ durch $7$ und erhalte $217 : 7 = 31$. Nach dem Test mit dem Sieb des Eratosthenes ist $31$ prim, denn $31$ ist durch keine der Zahlen $2$, $3$, $5$ oder $7$ teilbar. Wir erhalten also folgende Primfaktorzerlegung:

  $217= 7 \cdot 31$

• Analysiere die Funktionsweise des Siebs von Eratosthenes.

  Tipps

  Ist der kleinste Primfaktor einer Zahl $11$, so ist die Zahl entweder selbst $11$ oder größer als $100$.

  $1$ ist keine Primzahl. Daher besitzt jede Primzahl genau einen Primteiler.

  Die Faktoren einer Zahl sind nicht größer als die Zahl selbst.

  Lösung

  Die Primfaktorzerlegung ist zunächst für natürliche Zahlen definiert. Du kannst auch jede ganze Zahl in Primfaktoren zerlegen, indem du negative Primzahlen zulässt. In jedem Fall aber besitzt jede natürliche Zahl eine Primfaktorzerlegung. Diese Zerlegung ist eindeutig bis auf die Reihenfolge der Primfaktoren, denn die Primfaktoren ergeben sich in eindeutiger Weise durch die Division der Zahl durch ihre Teiler. Eine Zahl heißt Primzahl, wenn sie nur durch sich selbst und durch $1$ teilbar ist. Daher besitzt jede Primzahl genau zwei Teiler und jede Zahl, die genau zwei Teiler besitzt, ist eine Primzahl.

  Die Zahl $2$ hat die Teiler $1$ und $2$, ist also eine Primzahl. Der Teiler $2$ ist eine Primzahl und heißt deswegen Primteiler. $2$ ist der einzige Primteiler von $2$, denn $1$ ist keine Primzahl. Ähnliches gilt für die Teiler einer jeden Primzahl: Der einzige Primteiler einer Primzahl ist diese Primzahl selbst. Da jede gerade Zahl durch $2$ teilbar ist, ist $2$ die einzige gerade Primzahl.

  Kein Faktor eines Produkts ist größer als das Produkt selbst. Insbesondere ist jeder Primfaktor einer Zahl höchstens so groß wie die Zahl selbst.

  Quadrierst du eine Zahl, so kommt in der Quadratzahl jeder Primfaktor der quadrierten Zahl doppelt vor. Insbesondere hat jeder Primfaktor einer Quadratzahl in der Primfaktorzerlegung der Quadratzahl eine gerade Anzahl.

  Ist eine Zahl $<100$ das Produkt zweier Zahlen, so kann höchstens einer der beiden Faktoren $>10$ sein. Andernfalls wäre das Produkt $>100$. Enthält also eine Zahl zwischen $1$ und $100$ einen Primfaktor $> 10$, so ist die Zahl entweder selbst eine Primzahl oder sie enthält einen weiteren Primfaktor, der $<10$ ist.

  Anders ausgedrückt: Ist eine Zahl zwischen $1$ und $100$ keine Primzahl, sondern das Produkt zweier Zahlen $>1$, so enthält sie einen Primfaktor $<10$. Um die Primzahlen zwischen $1$ und $100$ zu finden, genügt es demnach, die Zahlen auf Primfaktoren $<10$ zu untersuchen. Enthält eine Zahl zwischen $1$ und $100$ keinen der Primfaktoren $2$, $3$, $5$ und $7$, so kann sie auch nicht mehr als einen Primfaktor $>10$ enthalten (sonst wäre sie $>100$). Streichst du also zwischen $1$ und $100$ alle Vielfachen der Primzahlen $2$, $3$, $5$ und $7$, so sind alle Zahlen, die übrig bleiben, Primzahlen.

• Vervollständige die Sätze.

  Tipps

  Eine Zahl heißt Primzahl, wenn sie nur durch sich selbst und durch $1$ teilbar ist.

  Die kleinste Primzahl ist $2$.

  Jede gerade Zahl ist durch $2$ teilbar.

  Lösung

  Eine Primzahl ist eine Zahl $>1$, die nur durch sich selbst und durch $1$ teilbar ist. Daher hat jede Primzahl genau zwei Teiler. Die Zahl $2$ ist die kleinste Primzahl und zugleich die einzige gerade Primzahl. Denn jede gerade Zahl $>2$ ist außer durch sich selbst und durch $1$ auch mindestens durch $2$ teilbar und daher keine Primzahl. Insbesondere ist außer $2$ jede Primzahl ungerade. Keine ungerade Zahl ist durch $2$ teilbar, denn die durch $2$ teilbaren Zahlen sind genau die geraden Zahlen.

  So erhältst du die folgenden richtigen Sätze:

  • „Jede Primzahl ... hat genau zwei Teiler.“

  • „Eine gerade Zahl außer $2$ ... ist keine Primzahl.“

  • „Keine ungerade Zahl ... ist durch $4$ teilbar.“

  • „Jede Primzahl außer $2$ ... ist ungerade.“

• Prüfe die Aussagen.

  Tipps

  Da $100 = 10 \cdot 10$ gilt, ist jede Zahl zwischen $1$ und $100$ mit Primfaktoren größer als $10$ eine Primzahl.

  Die Quadratzahl von $64=8^2$ hat die Primfaktorzerlegung:

  $64= 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2$

  Lösung

  Folgende Aussagen sind richtig:

  • „Jede Zahl zwischen $2$ und $100$ ist entweder eine Primzahl oder durch einen der Primfaktoren $2$, $3$, $5$ oder $7$ teilbar.“ Denn jede Zahl zwischen $1$ und $100$, die keine Primzahl ist, muss einen Primfaktor haben, der kleiner ist als $10$. Denn wäre mehr als ein Primfaktor größer als $10$, so wäre das Produkt größer als $100$.

  • „Hat eine zweistellige Zahl keinen einstelligen Primfaktor, so ist sie eine Primzahl.“ Zweistellig sind alle Zahlen, die größer als $9$ und kleiner als $100$ sind. Hat eine solche Zahl keinen einstelligen Primfaktor, so kann sie nicht das Produkt mehrerer Primfaktoren sein. Denn jede zweistellige Primzahl ist größer als $10$. Das Produkt zweier solcher Primzahlen wäre also größer als $100$ und damit nicht mehr zweistellig.

  • „Es gibt eine kleinste Primzahl, aber keine größte Primzahl.“ Die kleinste Primzahl ist $2$. Mit dem Sieb des Eratosthenes findest du zuerst alle Primzahlen von $1$ bis $100$. Die so gefundenen Primzahlen kannst du für ein Eratosthenes-Sieb bis $10 000 = 100^2$ verwenden. Um neue Primzahlen zu finden, kannst du das Sieb wieder erweitern. Weil dieses Verfahren nie endet, gibt es auch keine größte Primzahl.

  Folgende Aussagen sind falsch:

  • „Der größte Primfaktor einer Zahl ist höchstens so groß wie die Wurzel der Zahl.“ Ist die Zahl eine Primzahl, so ist sie mit ihrem größten Primfaktor identisch. Ist die Zahl keine Primzahl, so ist der kleinste Primfaktor höchstens so groß wie die Wurzel dieser Zahl. Beispielsweise hat $99$ die Faktoren $9$ und $11$, also die Primfaktoren $3$ und $3$ und $11$. Da $99<100$ gilt, ist auch $\sqrt{99} < \sqrt{100} = 10$. Der größte Primfaktor von $99$ ist aber $11 > 10 > \sqrt{99}$.

  • „Es gibt eine zweistellige Zahl mit $4$ verschiedenen Primfaktoren.“ Die kleinste Zahl mit $4$ verschiedenen Primfaktoren ist $2 \cdot 3 \cdot 5 \cdot 7 = 210$.