Nehmen wir eine positive ganze Zahl x. Wie können wir alle Primzahlen bis zu x finden? Eine Methode hierfür ist das Sieb des Eratosthenes, dessen Geschichte bis ins antike Griechenland zurückreicht. Die Schritte des Siebs des Eratosthenes sind wie folgt: Zuerst listet man alle ganzen Zahlen von 2 bis x auf und behält die Zahl 2 bei, während alle Vielfachen von 2 gestrichen werden. Im nächsten Schritt sind die Primzahlen nach der Zahl 2 die Zahl 3; diese wird behalten, während alle Vielfachen von 3 gestrichen werden. Im dritten Schritt sind die Primzahlen nach der Zahl 3 die Zahl 5; diese wird behalten, während alle Vielfachen von 5 gestrichen werden. So weiter, bis im vorletzten Schritt die nächstgelegene Primzahl, die nicht größer als x ist, behalten wird, während alle Vielfachen dieser Zahl gestrichen werden. Die verbleibende Liste enthält dann alle Primzahlen bis zu x. Diese Methode basiert auf der Tatsache, dass, wenn a keine Primzahl ist, a zwangsläufig einen Teiler hat, der nicht größer als ist.
Mit dem Sieb des Eratosthenes kann man relativ einfach eine Tabelle der Primzahlen erstellen. Was aber, wenn man eine nicht sehr große positive ganze Zahl a (zum Beispiel nicht größer als 10000) hat und gerade keinen Primzahltisch zur Hand hat, um zu überprüfen, ob a eine Primzahl ist? Tatsächlich reicht es aus, alle Primzahlen bis zu mit a zu dividieren, um dies zu überprüfen.