Primzahlen
Prüfe sofort, ob eine Zahl eine Primzahl ist (und finde ihren kleinsten Teiler, wenn sie keine ist), oder erstelle die vollständige Liste der Primzahlen bis 100.000.
So prüfst du, ob eine Zahl eine Primzahl ist
Eine Zahl ist eine Primzahl, wenn sie genau zwei Teiler hat: 1 und sich selbst. Um das zu prüfen, musst du nicht jede Zahl ausprobieren, es reicht, Teiler bis zur Quadratwurzel zu suchen, denn wenn n = a × b, muss mindestens einer der beiden Faktoren ≤ √n sein. Dieses Tool probiert 2 und 3, dann nur Kandidaten der Form 6k ± 1 (die einzigen möglichen Primzahlen größer als 3), deshalb ist die Prüfung selbst bei Zahlen bis zu einer Billion sofort fertig. Wenn die Zahl keine Primzahl ist, ist der kleinste gefundene Teiler immer selbst eine Primzahl.
Das Sieb des Eratosthenes, ein 2.200 Jahre alter Algorithmus
Die Liste wird mit der Methode des griechischen Mathematikers Eratosthenes erstellt: Du schreibst alle Zahlen bis zur Grenze auf und „siebst“ dann die Vielfachen jeder gefundenen Primzahl aus, beginnend bei ihrem Quadrat. Was übrig bleibt, ist eine Primzahl. Je höher du kommst, desto seltener werden Primzahlen: Es gibt 25 unter 100, 168 unter 1.000 und 9.592 unter 100.000, und trotzdem gehen sie, wie Euklid bewiesen hat, nie aus.