Der naheliegende Weg
Ist 97 eine Primzahl? Wir probieren der Reihe nach: Durch 2 geht nicht, durch 3 nicht, durch 4 nicht, durch 5 nicht … bis hinauf zu 96. Keiner teilt. Also ist 97 prim.
Das funktioniert — aber es waren 95 Versuche für eine zweistellige Zahl. Bei einer sechsstelligen Zahl wären es fast eine Million. Es muss besser gehen.
Die erste Abkürzung: nur ungerade Teiler
Wenn 2 nicht teilt, teilt auch 4 nicht, und 6 nicht, und 8 nicht. Jede gerade Zahl enthält ja die 2 als Faktor. Wir sparen damit die Hälfte aller Versuche. Dasselbe gilt für 3: Wenn 3 nicht teilt, braucht man 6, 9, 12 gar nicht erst zu probieren.
Es genügt, durch Primzahlen zu teilen. Denn jeder zusammengesetzte Teiler enthält selbst wieder einen Primteiler, und den hätten wir schon gefunden.
Die zweite Abkürzung: bis zur Wurzel genügt
Das ist der eigentliche Trick des Abends.
Nehmen wir an, 97 wäre zusammengesetzt, also 97 = a · b mit zwei Faktoren, die beide größer als 1 sind. Wären nun beide größer als 10, dann wäre ihr Produkt größer als 100 — und damit größer als 97. Das geht nicht. Also muss mindestens einer der beiden Faktoren kleiner oder gleich 10 sein.
Allgemein gilt: Ist n = a · b, so ist einer der beiden Faktoren höchstens √n.
Regel: Um zu prüfen, ob n prim ist, genügt es, die Primzahlen bis √n als Teiler zu testen. Findet sich keiner, ist n prim.
Für 97: √97 ≈ 9,8. Zu testen sind also nur 2, 3, 5 und 7 — vier Versuche statt 95. Und alle vier gehen nicht auf. 97 ist prim.
Für eine sechsstellige Zahl wie 999 983: √999983 ≈ 1000. Es sind die 168 Primzahlen bis 1000 zu testen statt einer Million Zahlen. Aus einer Million werden 168 Versuche.
Das Sieb des Eratosthenes
Die Regel von eben prüft eine Zahl. Will man dagegen alle Primzahlen eines Bereichs, gibt es etwas Besseres — und es ist rund 2 200 Jahre alt.
Eratosthenes von Kyrene, Leiter der Bibliothek von Alexandria, hatte diese Idee: Man schreibt alle Zahlen auf und streicht, statt zu prüfen.
- Schreibe die Zahlen von 2 bis 100 auf.
- Die erste ungestrichene Zahl ist 2. Sie ist prim. Streiche alle Vielfachen von 2: 4, 6, 8, 10, …
- Die nächste ungestrichene Zahl ist 3. Sie ist prim. Streiche 6, 9, 12, 15, … (manche sind schon weg, das macht nichts)
- Die nächste ungestrichene ist 5. Streiche 10, 15, 20, …
- Dann 7. Streiche 14, 21, 28, …
- Die nächste ungestrichene wäre 11 — aber 11² = 121 ist schon größer als 100. Wir sind fertig. Alles, was jetzt noch steht, ist prim.
Dass man bei 11 aufhören darf, ist wieder die Wurzelregel: Jede zusammengesetzte Zahl unter 100 hat einen Primteiler unter 10, und die sind alle abgearbeitet.
Übrig bleiben 25 Primzahlen:
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97
Warum das Sieb so gut ist
Beim Durchprobieren prüft man jede Zahl einzeln. Beim Sieb macht man gar keine Division — nur Addition. Von 2 zu 4 zu 6 zu 8 kommt man durch Weiterzählen. Das ist für einen Rechner die billigste Operation, die es gibt.
Dieser Vorsprung hat 2 200 Jahre gehalten. Moderne Varianten verlagern die Arbeit in kleinere Abschnitte, damit sie in den schnellen Speicher des Prozessors passen, aber die Idee von Eratosthenes steckt unverändert darin.
Ein Blick voraus
Zählen wir, wie viele Primzahlen in den ersten Hundertern liegen:
| Bereich | Anzahl |
|---|---|
| 1 – 100 | 25 |
| 101 – 200 | 21 |
| 201 – 300 | 16 |
| 301 – 400 | 16 |
| 401 – 500 | 17 |
Sie werden weniger. Nicht gleichmäßig, aber erkennbar. Wie schnell sie weniger werden, ist die Frage von Abend 4 — und eine der großen Fragen der Mathematik.
Am Rechner
Auf der Website unter Werkzeuge · Sieb des Eratosthenes läuft das Verfahren Schritt für Schritt ab. Machen Sie es erst mit Papier und Bleistift bis 100 — und sehen Sie es sich danach als Animation an. Es ist dasselbe, aber man sieht den Rhythmus der gestrichenen Vielfachen erst, wenn es sich bewegt.
Übungen
Wie findet man Primzahlen?
1. Führen Sie das Sieb des Eratosthenes auf Papier bis 50 durch. Wie viele Primzahlen bleiben übrig? Bei welcher Zahl durften Sie aufhören zu streichen, und warum?
2. Bis zu welchem Teiler muss man testen, um zu entscheiden, ob diese Zahlen prim sind? Geben Sie die Zahl an, nicht die Rechnung.
a) 211 b) 391 c) 1 849
3. Prüfen Sie mit der Wurzelregel, ob 211 eine Primzahl ist. Schreiben Sie jeden Versuch auf.
4. Die Zahl 391 ist nicht prim. Finden Sie ihre beiden Faktoren.
5. Wie viele Primzahlen gibt es bis 100? Und wie viele zwischen 100 und 200? Was fällt Ihnen auf?
6. Ein Schüler behauptet: „Um zu prüfen, ob 1 000 prim ist, muss ich durch alle Zahlen bis 500 teilen — die Hälfte genügt doch." Was ist an der Überlegung richtig, was falsch?
Zusatz. Die Zahl 323 sieht aus wie eine Primzahl. Ist sie es? Falls nicht: Warum fällt sie dem schnellen Hinsehen durch?
Lösungen anzeigen— erst selbst rechnen lohnt sich
1. Es bleiben 15 Primzahlen übrig:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Aufhören durfte man nach dem Streichen der Vielfachen von 7. Denn die nächste Primzahl wäre 11, und 11² = 121 liegt bereits über 50. Anders gesagt: √50 ≈ 7,07, also sind nur die Primzahlen bis 7 als Streicher nötig.
2.
| Zahl | √n | zu testen bis |
|---|---|---|
| a) 211 | ≈ 14,5 | 13 (die größte Primzahl ≤ 14,5) |
| b) 391 | ≈ 19,8 | 19 |
| c) 1 849 | = 43 genau | 43 |
Bei c) lohnt der Blick: 1 849 = 43². Die Wurzel geht auf, der Teiler ist also genau die Wurzel selbst.
3. 211 mit den Primzahlen bis 13 prüfen:
| Teiler | Rechnung | teilt? |
|---|---|---|
| 2 | 211 ist ungerade | nein |
| 3 | Quersumme 2+1+1 = 4 | nein |
| 5 | endet nicht auf 0 oder 5 | nein |
| 7 | 7 · 30 = 210, Rest 1 | nein |
| 11 | 11 · 19 = 209, Rest 2 | nein |
| 13 | 13 · 16 = 208, Rest 3 | nein |
Kein Teiler gefunden → 211 ist prim. Sechs Versuche statt 209.
4. 391 = 17 · 23
Rechenweg: 2, 3, 5, 7, 11, 13 teilen nicht. Bei 17 geht es auf: 17 · 23 = 391. Man war also schon fast bei der Grenze 19 angekommen — solche Zahlen sind die unangenehmen.
5. Bis 100: 25 Primzahlen. Zwischen 101 und 200: 21.
Auffällig: Es werden weniger, aber nicht dramatisch — gut ein Sechstel weniger im zweiten Hunderter. Dieses langsame Dünnerwerden ist genau das Thema von Abend 4.
6. Richtig ist der Grundgedanke, dass man nicht alle Zahlen bis 999 testen muss — kein Teiler kann größer als die Hälfte sein (außer der Zahl selbst).
Falsch ist die Grenze. Es genügt √1000 ≈ 31,6, also das Testen bis 31. Statt 500 Versuchen sind es elf (die Primzahlen 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31). Der Schüler hätte also rund 45-mal zu viel gerechnet.
Nebenbei: 1 000 = 2³ · 5³ ist natürlich schon beim ersten Versuch erledigt.
Zusatz. 323 = 17 · 19.
Sie fällt durch, weil sie ungerade ist, nicht auf 5 endet und die Quersumme 8 nicht durch 3 teilbar ist — die drei Tests, die man im Kopf macht, greifen alle nicht. Erst bei 17 geht es auf. Zahlen, die Produkt zweier benachbarter, mittelgroßer Primzahlen sind, sehen besonders „prim" aus. Genau darauf beruht übrigens die Verschlüsselung im Internet.