Primzahl

Eine Primzahl ist eine natürliche Zahl größer als 1, die nur die Teiler 1 und sich selbst besitzt. Beispiele sind 2, 3, 5 und 7; die Zahl 2 ist die kleinste Primzahl und zugleich die einzige gerade Primzahl. Alle anderen geraden Zahlen größer als 2 sind keine Primzahlen.

Der Fundamentalsatz der Arithmetik besagt, dass jede natürliche Zahl größer als 1 eindeutig als Produkt von Primzahlen geschrieben werden kann. In ihrer Geschichte zeigte Euclid, dass es unendlich viele Primzahlen gibt: Aus jeder endlichen Liste von Primzahlen lässt sich eine weitere Primzahl konstruieren.

Die Verteilung der Primzahlen ist nicht gleichmäßig, aber sie wird durch die Dichte der Primzahlen beschrieben. Die Funktion pi(x) – die Anzahl der Primzahlen ≤ x – erfüllt pi(x) ~ x / log x, was eine grobe Abschätzung der Häufigkeit von Primzahlen für große x liefert.

Primalitätstests prüfen, ob eine gegebene Zahl prim ist. Eine einfache Methode ist die Teilbarkeitsprüfung bis zur Quadratwurzel der Zahl; effizientere Algorithmen verwenden deterministische Tests für bestimmte Zahlenbereiche oder probabilistische Verfahren wie Miller-Rabin. Der theoretisch allgemeine AKS-Primzahlsatz beweist, dass Primalität in polynomialer Zeit entschieden werden kann. Die Siebung von Eratosthenes ist eine klassische Methode zur Auflistung aller Primzahlen bis zu einem gegebenen Grenzwert.

Primenzahlen spielen eine zentrale Rolle in der Zahlentheorie und finden Anwendungen in der Kryptographie, insbesondere bei Verfahren wie RSA, die auf großen Primzahlen basieren.