Primzahltest
Prüft, ob eine natürliche Zahl n ≥ 2 eine Primzahl ist (nur durch 1 und sich selbst teilbar).
Primzahltest berechnen
Prüft, ob eine natürliche Zahl n ≥ 2 eine Primzahl ist (nur durch 1 und sich selbst teilbar).
Was ist eine Primzahl?
Eine Primzahl ist eine natürliche Zahl n ≥ 2, die genau zwei Teiler hat: die 1 und sich selbst. Die ersten Primzahlen lauten 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 …
Jede Zahl ab 2, die keine Primzahl ist, heißt zusammengesetzt — sie lässt sich als Produkt kleinerer Zahlen schreiben (z. B. 21 = 3 · 7).
Die Formel
Der Primzahltest ist keine arithmetische Formel, sondern ein Verfahren — die Probedivision:
p = Primzahl(n)
n ist Primzahl ⇔ kein Teiler i mit 2 ≤ i ≤ √n teilt nIn der Praxis genügt es, alle Zahlen bis √n zu prüfen — größere Teiler hätten zwangsläufig einen Partner kleiner als √n. Mit der 6k ± 1-Optimierung überspringst du alle Vielfachen von 2 und 3:
Sonderfälle: n = 2, n = 3 → Primzahl
Ausschluss: n teilbar durch 2 oder 3 → keine Primzahl
Schleife: i = 5, 11, 17, … (i, i + 2 prüfen)
bis i · i > nDie Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| n | Zahl | — | Die zu prüfende natürliche Zahl. Verlangt wird n ≥ 2. |
| p | Aussage | — | Ergebnis als Text: „ist Primzahl" oder „ist keine Primzahl". |
Minimal-Beispiel
Ist 7 eine Primzahl?
√7 ≈ 2,65 → prüfe Teiler 2
7 / 2 = 3 Rest 1 → kein Teiler
Ergebnis: 7 ist PrimzahlPraxis-Beispiele
Beispiel 1 — 17 ist Primzahl
√17 ≈ 4,12 → prüfe 2, 3
17 ungerade → nicht durch 2 teilbar
17 / 3 = 5 Rest 2 → nicht durch 3 teilbar
Ergebnis: 17 ist PrimzahlBeispiel 2 — 21 ist keine Primzahl
√21 ≈ 4,58 → prüfe 2, 3
21 ungerade → nicht durch 2 teilbar
21 / 3 = 7 Rest 0 → Teiler gefunden
Ergebnis: 21 ist keine Primzahl (= 3 · 7)Beispiel 3 — 97 ist Primzahl
√97 ≈ 9,85 → prüfe 2, 3, 5, 7
97 / 2 = 48 Rest 1
97 / 3 = 32 Rest 1
97 / 5 = 19 Rest 2
97 / 7 = 13 Rest 6
Kein Teiler gefunden → 97 ist PrimzahlBeispiel 4 — 91 ist keine Primzahl (typische Stolperfalle)
91 wirkt auf den ersten Blick wie eine Primzahl, ist aber zusammengesetzt:
√91 ≈ 9,54 → prüfe 2, 3, 5, 7
91 / 7 = 13 Rest 0 → Teiler gefunden
Ergebnis: 91 ist keine Primzahl (= 7 · 13)