Eine Primzahl ist eine natürliche Zahl größer als 1, deren einzige positive Teiler 1 und sie selbst sind. Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23.
Primzahlen sind die multiplikativen Bausteine der ganzen Zahlen. Der Fundamentalsatz der Arithmetik besagt, dass jede ganze Zahl größer als 1 eine eindeutige Zerlegung in Primfaktoren besitzt (bis auf die Reihenfolge). Es gibt unendlich viele Primzahlen — Euklids Beweis aus der Zeit um 300 v. Chr. zählt noch heute zu den elegantesten Argumenten der Mathematik. Die Verteilung der Primzahlen wird logarithmisch dünner: nach dem Primzahlsatz liegt die Anzahl der Primzahlen unter \(n\) ungefähr bei \(n / \ln n\).
Primzahlen sind zentral für die moderne Kryptographie (RSA, elliptische Kurven), und die Suche nach sehr großen Primzahlen (insbesondere Mersenne-Primzahlen) treibt verteilte Rechenprojekte wie GIMPS seit Jahrzehnten an.