Auflistung aller Primzahlen in einem bestimmten Intervall.

Mit dem Sieb des Eratosthenes (Eratosthenes, Sieb des) lassen sich (mit Computerhilfe) recht umfangreiche Primzahltafeln in kurzer Zeit erzeugen (sofern die gesuchten Primzahlen nicht zu groß sind). Bevor es elektronische Rechner gab, publizierte Derrick Norman Lehmer 1914 eine recht zuverlässige Primzahltafel, die alle Primzahlen zwischen 2 und 10 006 721 enthält. Zuvor hatte Jacob Philip Kulik bereits eine 4212 Seiten umfassende Faktor- und Primzahltafel erstellt, die bis etwa 10⁸ reichte, aber recht unzuverlässig war.

Heutzutage ist man weniger an solchen Primzahltafeln interessiert, als an sehr großen Primzahlen, mit einigen hundert Dezimalstellen, und an der Faktorisierung solch großer Zahlen. In diesen Größenordnungen ist das Sieb des Eratosthenes wegen des zu schnellen Anwachsens der erforderlichen Rechenzeit nicht mehr tauglich. Aus dem mühevollen Aufstellen von Primzahltafeln entwickelte sich so ein interessanter Zweig der Zahlentheorie, der sich mit auf tiefliegenden zahlentheoretischen Methoden basierenden Algorithmen zum Auffinden großer Primzahlen und zum Faktorisieren großer Zahlen befaßt.