Die Primzahlen sind die natürlichen Zahlen, die außer durch 1 und sich selbst durch keine anderen natürlichen Zahlen teilbar sind. Also ist 1 eine Primzahl? Ist p eine natürliche Zahl größer als 1, dann wird p als Primzahl (oder Primfaktor) bezeichnet, wenn p nur die beiden Faktoren 1 und p hat. Das heißt, Primzahlen lassen sich nicht in das Produkt zweier kleinerer Faktoren zerlegen. Die Folge der Primzahlen lautet 2, 3, 5, 7, 11, 13, 17, 19, ...
Primzahlen sind wichtig, weil jede natürliche Zahl größer als 1 in ein Produkt aus Primzahlen zerlegt werden kann, und dieses Produkt ist eindeutig (wenn man die Reihenfolge der Faktoren ignoriert). Dieser Satz wird als „arithmetische Grundgesetz“ bezeichnet. Zum Beispiel kann 7623 in 3^2 × 7 × 11^2 zerlegt werden. Die Eindeutigkeit besagt, dass die Primfaktoren 3, 7 und 11 sowie ihre entsprechenden Quadratzahlen 2, 1 und 2 einzigartig sind und nicht durch andere Zahlen ersetzt werden können. Wir wissen, dass jede Quadratzahl von 1 gleich 1 ist. Wenn man 1 ebenfalls als Primzahl betrachtet, könnte man jede Potenz von 1 in die Zerlegung von 7623 einfügen, was die Eindeutigkeit der Zerlegung zerstören und zu unnötigen Schwierigkeiten führen würde. Daher haben Mathematiker festgelegt, dass 1 keine Primzahl ist.
Das arithmetische Grundgesetz zeigt, dass Primzahlen die „Grundbausteine“ der natürlichen Zahlen sind. Die Primzahltabelle ist für die Zahlentheorie genauso wichtig wie das Periodensystem für die Chemie, allerdings mit einem großen Unterschied: Die Primzahltabelle ist unendlich.