EMZETT.
Login

Emzett Wiki

Primzahlen und das Sieb des Eratosthenes: Rechnen mit Teilbarkeit

Properties1
tagsglossar, mathematik, algorithmen

2 Min. Lesezeit

Primzahlen und das Sieb des Eratosthenes: Rechnen mit Teilbarkeit

Kurz: Primzahlen sind nur durch 1 und sich selbst teilbar; mit dem Sieb des Eratosthenes findet man alle bis n schnell, und ihre Schwierigkeit beim Zerlegen sichert Verschlüsselung wie RSA.

Genauer: Eine Primzahl ist eine natürliche Zahl > 1 mit genau zwei Teilern (1 und sich selbst): 2, 3, 5, 7, 11, 13 … Jede Zahl lässt sich eindeutig in Primfaktoren zerlegen (Hauptsatz der Arithmetik): 360 = 2³ · 3² · 5.

Im Detail

Primzahltest

Naiv: n ist prim, wenn kein Teiler von 2 bis √n existiert (größere Teiler hätten einen kleinen Partner):

def ist_prim(n):
    if n < 2: return False
    if n % 2 == 0: return n == 2
    i = 3
    while i * i <= n:
        if n % i == 0: return False
        i += 2
    return True

Laufzeit O(√n). Für riesige Zahlen (RSA, 2048 Bit) nutzt man probabilistische Tests (Miller-Rabin) und AKS (deterministisch, polynomiell, aber langsam).

Sieb des Eratosthenes

Alle Primzahlen bis n: Liste 2..n, dann jeweils Vielfache der gefundenen Primzahl streichen.

def sieb(n):
    ist = [True] * (n + 1); ist[0:2] = [False, False]
    for p in range(2, int(n ** 0.5) + 1):
        if ist[p]:
            for k in range(p * p, n + 1, p):
                ist[k] = False
    return [i for i, b in enumerate(ist) if b]

Beispiel sieb(30) → 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Aufwand O(n log log n), Speicher O(n) (Bit-Array spart Platz). Streichen ab p², weil kleinere Vielfache schon durch kleinere Primzahlen gestrichen wurden.

Wichtige Begriffe

  • Teilbarkeitsregeln: durch 2 (gerade), 3 (Quersumme), 5 (Endziffer 0/5), 9, 11 (alternierende Quersumme).
  • ggT/kgV: Euklid; kgV = a·b / ggT.
  • Modulo (%) und Restklassen: Uhr-Rechnung, Hashfunktionen, Prüfziffern (IBAN, ISBN), Zyklen.
  • Primfaktorzerlegung: ggT/kgV, Brüche kürzen.
  • Mersenne-Primzahlen 2^p − 1 (größte bekannte Primzahlen), Primzahlzwillinge (11/13), Goldbachsche Vermutung (ungelöst).
  • Dichte: Anzahl Primzahlen ≤ n ≈ n / ln n.

Warum Primzahlen in der IT wichtig sind

  • RSA: Zwei große Primzahlen p, q werden multipliziert (n = p·q öffentlich); Faktorisierung von n ist schwer, das trägt die Sicherheit. Ein Quantencomputer (Shor-Algorithmus) könnte das knacken → Post-Quanten-Kryptografie.
  • Diffie-Hellman, elliptische Kurven: Modulare Arithmetik über Primzahlkörpern.
  • Hashtabellen: Größe oft Primzahl (bessere Streuung).
  • Zufallszahlengeneratoren, Prüfsummen.
  • Schlüsselerzeugung: Primzahlsuche mit Miller-Rabin (OpenSSL).
  • Prüfung (IHK): Teilbarkeit, Modulo, einfache Programme.

Siehe auch: Euklidischer Algorithmus, Big-O-Notation, Hashmap

Backlinks