Primzahlprüfer

Zuletzt aktualisiert: 2026-05-18

Definition

Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist. Es gibt also keinen anderen ganzzahligen Teiler.

• 2 ist prim: teilbar nur durch 1 und 2
• 7 ist prim: teilbar nur durch 1 und 7
• 12 ist zusammengesetzt: teilbar durch 1, 2, 3, 4, 6 und 12

Die ersten zwanzig Primzahlen:

$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71$

Primzahlen werden mit wachsenden Zahlen seltener — unterhalb von 100 gibt es 25, unterhalb von 1000 sind es 168 — aber sie hören nie auf. Euklid bewies um 300 v. Chr., dass es unendlich viele Primzahlen gibt.

Sonderfall 1

Intuitiv scheint 1 prim zu sein, weil es nur durch 1 und sich selbst teilbar ist. Die moderne Definition fordert jedoch genau zwei verschiedene positive Teiler, und 1 hat nur einen (sich selbst).

Der tiefere Grund liegt im Fundamentalsatz der Arithmetik: Jede ganze Zahl größer als 1 lässt sich eindeutig als Produkt von Primzahlen schreiben. Wäre 1 eine Primzahl, gäbe es unendlich viele Zerlegungen:

$12 = 2^2 \times 3 = 1 \times 2^2 \times 3 = 1^2 \times 2^2 \times 3 = \ldots$

Das würde die Eindeutigkeit zerstören. Die 1 wird als Einheit bezeichnet — weder prim noch zusammengesetzt.

Wie der Rechner funktioniert: Probedivision

Für Zahlen von 1 bis 1000 verwendet dieser Rechner Probedivision — die Überprüfung der Teilbarkeit durch alle Primzahlen bis $\sqrt{1000} \approx 31{,}6$. Hat eine Zahl $n$ keinen Primfaktor kleiner oder gleich ihrer Quadratwurzel, ist $n$ selbst prim.

Die Primzahlen bis 31 sind: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Durch Prüfung dieser elf Zahlen lässt sich die Primalität jeder Zahl bis 1000 feststellen.

Beispiel — ist 97 prim?

Divisor	$97 \div d$	Rest
2	48,5	1
3	32,3…	1
5	19,4	2
7	13,857…	6

Keine Primzahl bis $\sqrt{97} \approx 9{,}8$ teilt 97 ohne Rest — 97 ist prim.

Beispiel — ist 91 prim?

$91 \div 7 = 13$ mit Rest 0. Also ist 91 zusammengesetzt ($91 = 7 \times 13$), kleinster Primfaktor ist 7.

Das Sieb des Eratosthenes

Will man alle Primzahlen bis zu einer Schranke finden, ist das Sieb des Eratosthenes effizienter:

1. Zahlen von 2 bis $N$ auflisten
2. Vielfache von 2 streichen (4, 6, 8, …)
3. Zur nächsten nicht gestrichenen Zahl (3) gehen und deren Vielfache streichen
4. Wiederholen bis $\sqrt{N}$

Alle verbleibenden Zahlen sind prim. Die Zeitkomplexität beträgt $O(N \log \log N)$.

Primzahlen in der Kryptografie

Praktisch die gesamte asymmetrische Kryptografie beruht auf einer einfachen Asymmetrie: Zwei große Primzahlen zu multiplizieren erfordert minimalen Rechenaufwand; ihr Produkt in die Ursprungsfaktoren zu zerlegen ist praktisch unmöglich.

RSA-Verschlüsselung (HTTPS, digitale Signaturen):

1. Zwei große Primzahlen $p$ und $q$ wählen (typischerweise 1024–4096 Bit).
2. $n = p \times q$ berechnen und als Teil des öffentlichen Schlüssels veröffentlichen.
3. Ein Angreifer muss $n$ faktorisieren — das würde selbst mit modernsten Computern länger dauern als das Alter des Universums.

Diese Einwegfunktion ist das Fundament sicherer Kommunikation im Internet.

Kurzübersicht

Zahl	Prim?	Kleinster Primfaktor
1	Nein (Einheit)	—
2	Ja	2 (selbst)
4	Nein	2
17	Ja	17 (selbst)
49	Nein	7
97	Ja	97 (selbst)
100	Nein	2
997	Ja	997 (selbst)

Häufig gestellte Fragen (FAQ)

Was ist eine Primzahl?

Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist. Zum Beispiel sind 2, 3, 5, 7, 11 und 13 Primzahlen. Die Zahl 12 ist keine Primzahl, weil sie durch 2, 3, 4 und 6 teilbar ist. Jede ganze Zahl größer als 1 lässt sich eindeutig als Produkt von Primzahlen darstellen – das ist der Fundamentalsatz der Arithmetik.

Warum ist 1 keine Primzahl?

Eine Primzahl muss genau zwei positive Teiler haben: 1 und sich selbst. Die Zahl 1 hat nur einen einzigen positiven Teiler (sich selbst). Würde man 1 als Primzahl zählen, wäre die Primfaktorzerlegung nicht mehr eindeutig: 12 = 2² × 3 = 1 × 2² × 3 = 1² × 2² × 3 usw. – unendlich viele Zerlegungen für dieselbe Zahl.

Was sind die ersten zehn Primzahlen?

Die ersten zehn Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23 und 29. Die Zahl 2 ist die einzige gerade Primzahl; jede andere gerade Zahl ist durch 2 teilbar und damit keine Primzahl. Euklid bewies bereits um 300 v. Chr., dass es unendlich viele Primzahlen gibt.

Warum sind Primzahlen für die Kryptografie wichtig?

Die meisten asymmetrischen Verschlüsselungsverfahren – darunter RSA, das HTTPS und digitale Signaturen absichert – nutzen die Tatsache, dass das Multiplizieren zweier großer Primzahlen einfach ist, das Rückrechnen (Faktorisieren) des Produkts aber praktisch unmöglich. Typische RSA-Schlüssel verwenden Primzahlen mit Hunderten von Stellen.