In gewisser Weise bilden die Primzahlen die Bausteine, aus denen alle Zahlen bestehen. Dies verdeutlicht der Fundamentalsatz der Arithmetik: Jede natürliche Zahl größer als 1 hat eine eindeutige Primfaktorzerlegung, das heißt es gibt Primzahlen deren Produkt genau die Ausgangszahl ist, und diese Primzahl sind eindeutig bestimmt.
Nun stellt sich uns die Frage, wieviele Primzahlen es gibt? Der grieschische Mathematiker Euklid bewies, daß es unendlich viele Primzahlen gibt. Als Beweis führte folgendes Argument: Wir nehmen an, es gäbe nur endlich viele Primzahlen. Dann betrachten wir das Produkt all dieser Primzahlen und zählen 1 dazu. Die so erhaltene Zahl ist dann keine Primzahl, aber liefert bei Division durch eine Primzahl den Rest 1, hat also keine Primfaktoren. Das ist ein Widerspruch, also gibt es unendlich viele Primzahlen.
Diese Frage, wie man Primzahlen findet, beantwortete Eratosthenes im dritten Jahrhundert vor Christi. Dazu ging er wie folgt vor: Man schreibe sich der Reihe die natürlichen Zahlen größer 1 auf. Die erste Zahl in dieser Folge ist 2 - die erste Primzahl. Nun streiche man alle Vielfachen von 2 (also 2, 4, 6, 8, 10, ...) aus der Folge, dann ist die erste nicht ausgestrichene Zahl die 3, die nächste Primzahl. In der restlichen Folge streicht man nun die Vielfachen von 3, und erhält als erste nicht gestrichene Zahl die nächste Primzahl. Durch wiederholen des Verfahren erhält man der Reihe nach die Primzahlen. Wir nennen diese Methode nach seinem Erfinder das Sieb von Eratosthenes.
Nun, da es unendlich viele Primzahlen gibt, stellt sich uns die Frage,
wie "häufig" Primzahlen sind?
Dazu sei P(n) die Anzahl der Primzahlen kleiner einer gegebenen Zahl n,
dann gilt der folgende Satz von Charles de la Vallee-Poussin und Jacques Hadamard:
Beide Beweise stützen sich auf eine Abschwächung der Riemannschen Vermutung, nämlich das die Riemannsche Zeta-Funktion keine Nullstellen mit Realteil 1 hat. Die vollständige Riemannsche Vermutung besagt, daß die Nullstellen der Zeta-Funtion mit Realteil zwischen 0 und 1 alle auf der Geraden 0.5 + it liegen!
