Primzahlen

Was sind Primzahlen?

Primzahlen sind natürliche Zahlen größer als 1, die nur durch 1 und sich selbst ohne Rest teilbar sind. Sie sind die „Bausteine" aller natürlichen Zahlen.

Die ersten 100 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, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541

Primzahltest-Algorithmus

So prüfen Sie, ob n prim ist:

1. n = 1? → Keine Primzahl
2. n = 2? → Primzahl
3. n gerade? → Keine Primzahl
4. Teile n durch alle ungeraden Zahlen von 3 bis √n
5. Keine Teilung ohne Rest? → Primzahl

Sieb des Eratosthenes

Effizienter Algorithmus zum Finden aller Primzahlen bis n:

1. Liste aller Zahlen von 2 bis n erstellen
2. Kleinste nicht gestrichene Zahl (p) ist prim
3. Alle Vielfachen von p streichen (2p, 3p, ...)
4. Wiederholen bis p² > n

Primfaktorzerlegung

Jede natürliche Zahl > 1 lässt sich eindeutig als Produkt von Primzahlen darstellen (Fundamentalsatz der Arithmetik):

60 = 2² × 3 × 5
84 = 2² × 3 × 7
100 = 2² × 5²
1000 = 2³ × 5³

Besondere Primzahlen

• Zwillingsprimzahlen: Differenz 2 (z.B. 11 und 13)
• Mersenne-Primzahlen: Form 2ⁿ-1 (z.B. 31 = 2⁵-1)
• Fermat-Primzahlen: Form 2^(2ⁿ)+1
• Sophie-Germain: p und 2p+1 beide prim

Primzahlen in der Kryptographie

RSA-Verschlüsselung basiert auf der Schwierigkeit, große Zahlen in Primfaktoren zu zerlegen. Sichere Schlüssel verwenden Primzahlen mit Hunderten von Stellen.

Häufig gestellte Fragen

Warum ist 1 keine Primzahl?

Per Definition nicht. Würde 1 als prim gelten, wäre die Primfaktorzerlegung nicht eindeutig: 6 = 2×3 = 1×2×3 = 1×1×2×3...

Gibt es unendlich viele Primzahlen?

Ja! Euklid bewies dies schon vor 2300 Jahren: Angenommen es gäbe endlich viele. Dann bilde p₁×p₂×...×pₙ+1 – diese Zahl ist durch keine bekannte Primzahl teilbar → Widerspruch.

Was ist die größte bekannte Primzahl?

Eine Mersenne-Primzahl mit über 24 Millionen Stellen (Stand 2024): 2⁸²⁵⁸⁹⁹³³-1. Das GIMPS-Projekt sucht nach noch größeren.