Primzahl

Ganze Zahlen n ≥ 2 mit genau zwei positiven Teilern (siehe Teilbarkeit) heißen Primzahlen. Alle anderen Zahlen heißen zusammengesetzt. Ist n eine Primzahl so sind die einzigen Teiler 1 und n.

Eine qualitative Aussage darüber, wieviele Primzahlen es gibt, macht der Satz von Euklid.

Der Primzahlsatz macht eine quantitative Aussage über die Zahl π(x), die Zahl der Primzahlen kleiner oder gleich x: Für x gegen unendlich ist π(x) ∙ ln(x) / x = 1. Das bedeutet, dass die Funktionen π(x) und x → x / ln(x) asymptotisch gleich sind.