[348] Prīmzahl, in der Arithmetik jede solche ganze Zahl, die nur durch die Einheit und durch sich selbst, sonst aber durch keine ganze Zahl teilbar ist. Jede ganze Zahl, die keine P. ist, heißt zusammengesetzt. Primzahlen sind: 1, 2, 3, 5, 7, 11, 13, 17, 19 etc., dagegen ist z. B. 6 eine zusammengesetzte Zahl, weil sie durch 2 und durch 3 teilbar ist. Wie schon Euklid bewiesen hat, gibt es unendlich viele Primzahlen, es ist aber noch nicht gelungen, ein allgemeines Gesetz für ihre Verteilung in der Zahlenreihe zu finden. Dagegen kann man durch eine endliche Anzahl von Versuchen alle Primzahlen finden, die kleiner sind als irgend eine gegebene Zahl, z. B. als 100; dazu dient das Verfahren, das den Namen Sieb des Eratosthenes (cribrum Eratosthenis) führt. Man schreibt alle Zahlen von 1 bis 100 auf, streicht dann alle Vielfachen von 2 weg, hierauf unter den übriggebliebenen alle Vielfachen von 3, unter den noch übrigen alle Vielfachen von 5 etc. Man findet so außer den vorhin genannten Primzahlen noch: 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Will man feststellen, ob eine gegebene Zahl, z. B. 349, eine P. ist oder nicht, so braucht man nur alle Primzahlen aufzusuchen, die nicht größer als √349 sind, und nachzusehen, ob 349 durch eine von diesen (es sind hier 3, 5, 7, 11, 13, 17) teilbar ist; man findet so, daß 349 eine P. ist. Es gibt Primzahltafeln, in denen alle Primzahlen bis zur neunten Million verzeichnet sind, namentlich hat Dase solche Tafeln berechnet. Eine Näherungsformel für die Anzahl aller Primzahlen unter einer gegebenen Grenze hat zuerst Riemann 1859 angegeben; vgl. Meißel in den »Mathematischen Annalen«, Bd. 2 u. 3, und v. Mangoldt in Crelles »Journal«, Bd. 114, 1895. – Im Gegensatz zu den besprochenen Primzahlen, die man auch absolute Primzahlen nennt, bezeichnet man zwei ganze Zahlen dann als relative Primzahlen oder kürzer als teilerfremd, wenn es außer der Einheit keine ganze Zahl gibt, durch die sie beide teilbar sind.