Primzahlen bis 1000: Liste, Erkennen und Prüfen

Eine natürliche Zahl kann verschiedene positive Teiler besitzen. Ein Teiler passt ohne Rest in die Zahl. Die Zahl 7 ist prim, denn ihre einzigen positiven Teiler sind 1 und 7. Die Zahl 12 ist nicht prim: Neben 1 und 12 hat sie zum Beispiel die Teiler 2, 3, 4 und 6. Eine natürliche Zahl größer als 1, die nicht prim ist, heißt zusammengesetzte Zahl. Sie lässt sich als Produkt kleinerer natürlicher Zahlen größer als 1 schreiben. So gilt 12=3\cdot4. Warum kann keine andere gerade Zahl prim sein? Jede gerade Zahl größer als 2 ist durch 2 teilbar. Sie besitzt daher außer 1 und sich selbst noch mindestens einen weiteren Teiler.

Die folgende Tabelle enthält alle 168 Primzahlen von 2 bis 997. Die Einteilung nach Hunderterbereichen erleichtert das Nachschlagen. Zwischen 2 und 1000 liegen insgesamt 999 natürliche Zahlen. Davon sind 168 prim und 999-168=831 zusammengesetzt. Die Zahl 1000 gehört zu den zusammengesetzten Zahlen, denn beispielsweise gilt 1000=10\cdot100.

Bei einer kleinen Zahl kannst du mögliche Teiler ausprobieren. Bei größeren Zahlen wäre es jedoch unnötig, alle kleineren Zahlen zu testen. Für eine Zahl n genügt es, mögliche Primteiler bis zur Quadratwurzel \sqrt n zu prüfen. Du brauchst dabei nur Primzahlen als mögliche Teiler zu testen. Warum reicht das? Ist n=a\cdot b zusammengesetzt und wäre sowohl a>\sqrt n als auch b>\sqrt n, dann wäre a\cdot b>n. Das ist unmöglich. Bei einer zusammengesetzten Zahl muss daher mindestens ein Faktor höchstens \sqrt n sein. Bei 997 liegt die Quadratwurzel zwischen 31 und 32, denn 31^2=961 und 32^2=1024. Für einen vollständigen Test musst du deshalb nur die Primzahlen bis 31 prüfen. Keine davon teilt 997 ohne Rest; daher ist 997 prim.

Wenn du alle Primzahlen bis zu einer Grenze suchst, kannst du ein Siebverfahren verwenden. Dabei streichst du schrittweise die Vielfachen bereits gefundener Primzahlen. So findest du alle Primzahlen bis 30: Schreibe die natürlichen Zahlen von 2 bis 30 auf. Behalte 2 und streiche alle größeren Vielfachen von 2. Die nächste nicht gestrichene Zahl ist 3. Behalte sie und streiche ihre größeren Vielfachen. Die nächste nicht gestrichene Zahl ist 5. Behalte sie und streiche ihre größeren Vielfachen. Alle nicht gestrichenen Zahlen sind prim. Beim Sieben bis 1000 führst du das Streichen mit der jeweils nächsten nicht gestrichenen Primzahl fort. Es genügt, neue Streichschritte für Primzahlen bis 31 zu beginnen, weil 32^2 bereits größer als 1000 ist. Die nicht gestrichenen Zahlen ergeben genau die vollständige Liste dieser Seite.