numbers Primzahlenliste & Prüfung star

So funktioniert es

Das Tool wechselt zwischen zwei verschiedenen Algorithmen, die jeweils zu einer anderen Frage passen. Der Listenmodus findet mit dem Sieb des Eratosthenes jede Primzahl bis zu einer Obergrenze — einem der ältesten noch alltäglich genutzten Algorithmen (zurückgeführt auf den griechischen Mathematiker Eratosthenes, 3. Jahrhundert v. Chr.). Ausgehend von 2 werden alle Vielfachen von 2 als zusammengesetzt markiert, dann geht es zur nächsten unmarkierten Zahl (3) und deren Vielfache werden markiert, dann zur nächsten unmarkierten Zahl (5) und so weiter. Was übrig bleibt, sobald die Quadratwurzel der Obergrenze erreicht ist, ist eine Primzahl. Kleines Beispiel: Um bis 30 zu sieben, streichen Sie die Vielfachen von 2 (4, 6, 8, …), dann die Vielfachen von 3 (6, 9, 12, …, einige bereits gestrichen), dann die Vielfachen von 5 (10, 15, …) — da 5×5=25 ≤ 30, aber 7×7=49 > 30, können Sie dort aufhören; was übrig bleibt — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — ist die vollständige Liste. Das läuft in O(n log log n) Zeit, bleibt also auch schnell, wenn der Bereich in die Hunderttausende wächst.

Der Prüfmodus beantwortet eine andere Frage — ist diese eine bestimmte Zahl eine Primzahl? — mittels Probedivision bis zur Quadratwurzel. Um zu testen, ob n eine Primzahl ist, genügt es, Teiler von 2 bis √n zu prüfen. Die Begründung: Wäre n = a × b mit a und b beide größer als √n, dann wäre a × b größer als n, was unmöglich ist. Also muss mindestens einer der beiden Faktoren √n oder kleiner sein, und er wird gefunden, bevor die Schleife endet. Beispiel: Um 97 zu prüfen, müssen Sie nur die Teilbarkeit durch 2, 3, 5, 7 testen (da 9² = 81 ≤ 97, aber 10² = 100 > 97) — keiner teilt glatt, also ist 97 eine Primzahl.

Was Sie wissen sollten

Die beiden Modi existieren, weil sie unterschiedliche Kompromisse eingehen: Das Sieb ist effizient, um viele Primzahlen auf einmal zu erzeugen, verschwendet aber Speicher und Zeit, wenn es Ihnen nur um eine einzige Zahl nahe einer riesigen Obergrenze geht; die Probedivision ist effizient für eine einzelne Prüfung, aber viel zu langsam, wenn sie für jede Zahl in einem großen Bereich einzeln wiederholt wird. Das jeweils passende Verfahren für die Aufgabe zu wählen, ist genau der Grund, warum dieses Tool beide anbietet.

• Die 1 wird per Definition und Konvention von den Primzahlen ausgeschlossen — sie hat nur einen Teiler, nicht zwei, was die Eindeutigkeit der Primfaktorzerlegung verletzen würde, wäre sie zugelassen.
• Die 2 ist die einzige gerade Primzahl; jede andere gerade Zahl ist durch 2 teilbar und daher zusammengesetzt.
• Mit wachsenden Zahlen werden Primzahlen im Durchschnitt seltener, hören aber nie auf zu erscheinen — Euklid bewies vor über zweitausend Jahren, dass es unendlich viele gibt.