Eine Primzahl ist eine ganze Zahl größer als 1, die genau zwei Faktoren hat: 1 und sich selbst. Primzahlen sind die Bausteine aller ganzen Zahlen – jede ganze Zahl kann als Produkt von Primzahlen ausgedrückt werden.
Die ersten 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
Beachten Sie, dass 2 die einzige gerade Primzahl ist. Alle anderen geraden Zahlen sind durch 2 teilbar.
Methode 1: Probeaufteilung
Der einfachste Weg, um zu testen, ob eine Zahl eine Primzahl ist, besteht darin, zu prüfen, ob eine Zahl bis zur Quadratwurzel sie gleichmäßig teilt.
Wichtige Erkenntnis: Wenn n einen Faktor größer als √n hat, gibt es auch einen entsprechenden Faktor kleiner als √n. Sie müssen also nur bis zu √n prüfen.
Algorithmus:
- Wenn n < 2, keine Primzahl
- Wenn n = 2, prim
- Wenn n gerade ist (außer 2), keine Primzahl
- Überprüfen Sie alle ungeraden Zahlen von 3 bis √n
- Wenn überhaupt, teile n gleichmäßig, nicht prim
- Ansonsten grundieren
Beispiel: Ist 97 eine Primzahl?
√97 ≈ 9,85, also Primzahlen bis 9 prüfen: 2, 3, 5, 7
- 97 ÷ 2 = 48,5 (nicht ganz)
- 97 ÷ 3 = 32,33... (nicht ganz)
- 97 ÷ 5 = 19,4 (nicht ganz)
- 97 ÷ 7 = 13,86 (nicht ganz)
Keine Teiler gefunden – 97 ist eine Primzahl.
Beispiel: Ist 91 eine Primzahl?
√91 ≈ 9,54, prüfen bis 9: 2, 3, 5, 7
- 91 ÷ 7 = 13 (ganze Zahl!)
91 ist keine Primzahl – 91 = 7 × 13.
Methode 2: Sieb von Eratosthenes
Das Sieb des Eratosthenes findet alle Primzahlen bis zu einem bestimmten Grenzwert. Es ist schnell und elegant und wurde um 240 v. Chr. vom griechischen Mathematiker Eratosthenes erfunden.
Um alle Primzahlen bis 50 zu finden:
- Schreiben Sie die Zahlen 2 bis 50 auf
- Beginnen Sie mit 2 (erste Primzahl). Streichen Sie alle Vielfachen von 2 (4, 6, 8...) durch.
- Gehen Sie zur nächsten ungekreuzten Zahl: 3. Streichen Sie Vielfache von 3 durch (9, 15, 21...)
- Weiter ungekreuzt: 5. Vielfache von 5 (25, 35...) durchstreichen
- Weiter ungekreuzt: 7. Vielfache von 7 durchstreichen (49...)
- Stoppen Sie, wenn Sie √50 ≈ 7,07 erreichen
- Alle übrigen ungekreuzten Zahlen sind Primzahlen
Primzahlen bis 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Primzahlen bis 100: Vollständige Liste
| Reichweite | Primzahlen |
|---|---|
| 1–10 | 2, 3, 5, 7 |
| 11–20 | 11, 13, 17, 19 |
| 21–30 | 23, 29 |
| 31–40 | 31, 37 |
| 41–50 | 41, 43, 47 |
| 51–60 | 53, 59 |
| 61–70 | 61, 67 |
| 71–80 | 71, 73, 79 |
| 81–90 | 83, 89 |
| 91–100 | 97 |
Es gibt 25 Primzahlen unter 100.
Schnelle Teilbarkeitstests
Bevor Sie eine vollständige Division durchführen, überprüfen Sie diese Regeln:
| Teilbar durch | Wenn... |
|---|---|
| 2 | Letzte Ziffer ist gerade (0,2,4,6,8) |
| 3 | Summe der durch 3 teilbaren Ziffern |
| 5 | Die letzte Ziffer ist 0 oder 5 |
| 7 | Keine einfache Regel – einfach teilen |
| 11 | Durch 11 teilbare Wechselziffernsumme |
Beispiel: Ist 143 eine Primzahl?
- Nicht einmal ✓
- 1+4+3 = 8, nicht durch 3 teilbar ✓
- Endet nicht mit 0 oder 5 ✓
- √143 ≈ 11,96, prüfen Sie bis 11
- 143 ÷ 7 = 20,43 ✓
- 143 ÷ 11 = 13 — teilbar!
143 = 11 × 13. Nicht prim.
Warum Primzahlen wichtig sind
Kryptographie: RSA-Verschlüsselung – zur Sicherung von Internet-Banking, HTTPS und E-Mail – basiert auf der Tatsache, dass die Multiplikation zweier großer Primzahlen einfach ist, die Rückrechnung des Ergebnisses in Primzahlen jedoch äußerst schwierig ist.
Informatik: Hash-Tabellen, Zufallszahlengeneratoren und Prüfsummen nutzen Eigenschaften von Primzahlen.
Reine Mathematik: Die Verteilung von Primzahlen bleibt eines der tiefgreifendsten ungelösten Probleme der Mathematik – die Riemann-Hypothese.
Interessante Prime-Fakten
- Die größte bekannte Primzahl (Stand 2024) hat über 41 Millionen Ziffern
- Primzahlzwillinge sind Primzahlen, die sich um 2 unterscheiden (11 und 13, 17 und 19, 41 und 43)
- Es gibt unendlich viele Primzahlen – bewiesen durch Euklid um 300 v. Chr
- Goldbachs Vermutung (seit 1742 unbewiesen): Jede gerade Zahl > 2 ist die Summe zweier Primzahlen