Primzahlen — die Atome der Zahlen
Definition · Primzahl
Eine natürliche Zahl > 1, die nur durch 1 und sich selbst teilbar ist.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, ...Euklid bewies (≈ 300 v.Chr.)Es gibt unendlich viele Primzahlen. Beweis: Angenommen es gibt nur endlich viele p₁, ..., pₙ. Dann ist N = p₁·p₂·...·pₙ + 1 entweder selbst prim oder hat einen Primfaktor, der nicht in der Liste steckt → Widerspruch.
Primfaktorzerlegung
Jede natürliche Zahl > 1 lässt sich eindeutig als Produkt von Primzahlen schreiben (Fundamentalsatz der Arithmetik):
60 = 2² · 3 · 5
84 = 2² · 3 · 7
1001 = 7 · 11 · 13Sieb des Eratosthenes
Klassischer Algorithmus zur Primzahlbestimmung bis zu einer Schranke n:
- Schreibe alle Zahlen 2 bis n auf.
- Nimm die kleinste verbliebene Zahl p (zuerst 2).
- Streiche alle Vielfachen von p.
- Wiederhole bis p² > n.
- Was übrig bleibt, sind die Primzahlen.