HandyTools Hub

Primzahl-Tools

Primzahlen prüfen, Faktoren finden, Primzahlbereiche generieren

100% clientseitige Verarbeitung

97 is a prime number

2^2 x 3 x 5

The 10th prime is 29

Prime Number Tools bündelt vier Rechner auf einer Seite: prüfen, ob eine Zahl prim ist, sie in Primfaktoren zerlegen, alle Primzahlen in einem Bereich auflisten oder die n-te Primzahl finden. Das ist nützlich für Hausaufgaben, für Übungen zu Mathematikwettbewerben, zum Kürzen von Brüchen oder einfach, um nachzusehen, ob eine Zahl, die Sie interessiert, prim ist. Wechseln Sie den Modus über die Schaltflächen oben; das Ergebnis des aktiven Modus aktualisiert sich beim Tippen, und jedes Ergebnis hat eine eigene Kopierschaltfläche.

Die vier Modi

ModusEingabeAusgabe
PrimzahlprüfungEine einzelne ZahlPrim oder zusammengesetzt, bei Primzahlen zusätzlich die nächstgelegenen Primzahlen
PrimfaktorenEine einzelne ZahlZerlegung mit Exponenten und Anzahl verschiedener Faktoren
Primzahlen im BereichZwei durch ein Komma getrennte GrenzenJede Primzahl dazwischen und die Anzahl
n-te PrimzahlEine Position wie 10Die Primzahl an dieser Position

Der Prüfmodus meldet zusätzlich für jede Primzahl die nächste und die vorherige Primzahl und sucht dafür bis zu 200 Stellen voraus. Das ist praktisch, wenn Sie eine nahe gelegene Primzahl für eine Hash-Tabellengröße oder für ein Beispiel brauchen und keine durch Ausprobieren auswählen möchten.

Wie der Primzahltest funktioniert

Jede Primzahl größer als 3 hat die Form 6k − 1 oder 6k + 1, sodass der Prüfer nicht jede ganze Zahl testen muss. Er verwirft zunächst Zahlen kleiner oder gleich 1, akzeptiert 2 und 3, verwirft alles, was durch 2 oder 3 teilbar ist, und testet dann die Teiler 5, 7, 11, 13, 17, 19 und so weiter in 6er-Schrittpaaren. Der Test endet, sobald das Quadrat des Teilers die Zahl übersteigt, denn eine zusammengesetzte Zahl hat immer einen Faktor, der nicht größer als ihre Quadratwurzel ist. Das Überspringen der Vielfachen von 2 und 3 entfernt rund zwei Drittel der Teilerkandidaten, was Einzelprüfungen selbst bei Eingaben im Millionenbereich schnell hält.

Praxisbeispiele

  1. 97 prüfen: Die Quadratwurzel ist etwa 9,85, also müssen nur 5 und 7 getestet werden; keine von beiden teilt die Zahl, also ist 97 prim. Das Tool meldet außerdem die nächste Primzahl 101 und die vorherige 89.
  2. 91 prüfen: Der Test mit 5 scheitert, der mit 7 gelingt, denn 91 = 7 × 13, also ist 91 zusammengesetzt. Der Faktormodus liefert 7 × 13.
  3. 60 zerlegen: 2^2 × 3 × 5, denn 60 = 2 × 2 × 3 × 5. Das Tool meldet zusätzlich, dass es 3 verschiedene Faktoren sind.
  4. Bereich 1,100: 25 Primzahlen, beginnend mit 2, 3, 5, 7, 11 und endend mit 89, 97.
  5. n-te Primzahl 10: Die 10. Primzahl ist 29. Die Folge beginnt 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Primfaktorzerlegung und der Fundamentalsatz

Der Fundamentalsatz der Arithmetik besagt, dass jede ganze Zahl größer als 1 genau eine Primfaktorzerlegung hat. Diese Eindeutigkeit ist der Grund, warum 91 immer zu 7 × 13 wird, egal wie Sie vorgehen, und warum das Tool Exponenten als Kurzschreibweise zeigen kann: 2^2 × 3 × 5 bedeutet zwei Zweien, eine Drei und eine Fünf. Dieselbe Zerlegung treibt praktische Arbeit an, etwa das Kürzen von Brüchen, das Finden des größten gemeinsamen Teilers und die Berechnung des kleinsten gemeinsamen Vielfachen — all das läuft auf den Vergleich von Primfaktoren hinaus. Die Faktorisierung ist zugleich die Asymmetrie hinter der RSA-Verschlüsselung: Zwei große Primzahlen zu multiplizieren ist billig, sie aus dem Produkt zurückzugewinnen dagegen schwer.

Den passenden Modus wählen

  • Nutzen Sie die Primzahlprüfung, wenn Sie eine Zahl und eine Ja-oder-Nein-Frage haben, besonders wenn Sie auch die benachbarten Primzahlen möchten.
  • Nutzen Sie die Primfaktoren, wenn Sie die Zerlegung selbst brauchen, etwa zum Kürzen eines Bruchs oder um Zahlen über ihre Bausteine zu vergleichen.
  • Nutzen Sie Primzahlen im Bereich, wenn Sie eine Liste brauchen, etwa die Primzahlen unter 1.000 für eine Programmierübung.
  • Nutzen Sie die n-te Primzahl, wenn Sie die Position kennen, aber nicht den Wert, etwa die 100. Primzahl.

Primzahlen in der Praxis

Jenseits von Rechenübungen haben Primzahlen echtes praktisches Gewicht. RSA und ähnliche Public-Key-Systeme beruhen auf der Kluft zwischen leichter Multiplikation und schwerer Faktorisierung. Hash-Tabellen verwenden oft eine Primzahl als Anzahl der Buckets, damit sich die Schlüssel beim Modulo-Hashing gleichmäßiger verteilen. Zikaden der Gattung Magicicada erscheinen in 13- und 17-Jahres-Zyklen, beide prim, was die Wahrscheinlichkeit verringert, mit dem kürzeren Zyklus eines Räubers zu synchronisieren. Selbst das einfache Kürzen eines Bruchs ist Faktorisierung im Verborgenen: 84/126 zu reduzieren bedeutet, die gemeinsame 2 × 3 × 7 zu finden und zu kürzen.

Grenzen und Randfälle

  • Die Modi Bereich und n-te Primzahl arbeiten mit roher Gewalt. Der Bereichsmodus prüft jede ganze Zahl der Reihe nach statt zu sieben, und der n-te-Primzahl-Modus zählt Primzahl für Primzahl nach oben, sodass große Bereiche oder sehr große Positionen länger dauern.
  • Die Faktorisierung verwendet den Absolutbetrag der Eingabe, eine negative Zahl meldet also dieselben Faktoren wie ihr positives Gegenstück, während die Primzahlprüfung negative Werte als zusammengesetzt meldet.
  • Dezimaleingaben werden geparst statt abgelehnt, doch die Primzahleigenschaft ist nur für ganze Zahlen definiert; lesen Sie ein Dezimalergebnis also nicht als sinnvoll.
  • Die Bereichseingabe verwendet ein Komma zwischen den beiden Grenzen; die Trim-Funktion fängt Leerzeichen ab, ein fehlendes oder zusätzliches Komma löst jedoch einen Fehler aus, statt zu raten.
  • Es gibt keinen Cache und keinen Export über die Kopierschaltflächen hinaus und keine Möglichkeit, eine Liste zwischen Seitenaufrufen zu speichern.

Verwandte Tools

Häufig gestellte Fragen

Welchen Primzahltest verwendet das Tool, und wie schnell ist er?

Es nutzt die Versuchsdivision mit der 6k±1-Optimierung: Nach dem Ausschluss von 2 und 3 prüft es die Teilerkandidaten 5, 7, 11, 13 und so weiter, und zwar nur bis zur Quadratwurzel der Zahl. Für eine einzelne Zahl ist das schnell, selbst bei Werten im Millionenbereich.

Warum dauert die Faktorisierung einer sehr großen Zahl manchmal lange?

Die Faktorisierung läuft ohne Sieb oder fortgeschrittene Verfahren durch ungerade Teiler bis zur Quadratwurzel des Restwerts. Eine Zahl mit zwei großen, dicht beieinanderliegenden Primfaktoren erzwingt viele Divisionen, deshalb können sehr große Eingaben langsam werden.

Ist 2 die einzige gerade Primzahl?

Ja. Jede gerade Zahl größer als 2 ist durch 2 teilbar, also ist 2 die einzige gerade Primzahl. Der Prüfer setzt das um, indem er alle geraden Zahlen über 2 sofort ausschließt.

Was zeigt die Faktorisierung von 1?

1 wird als Sonderfall behandelt und einfach als 1 angezeigt. Es werden keine Primfaktoren zugewiesen, was dazu passt, dass 1 keine Primzahl ist.

Worin unterscheiden sich der Bereichs- und der n-te-Primzahl-Modus?

Der Bereichsmodus nimmt zwei Grenzen und listet jede Primzahl dazwischen auf, samt Anzahl. Der n-te-Primzahl-Modus nimmt eine einzige Position und liefert die Primzahl an dieser Stelle, wobei die 1. Primzahl 2 und die 10. 29 ist.

Kann ich eine Dezimalzahl oder eine negative Zahl eingeben?

Der Zahlenparser akzeptiert Dezimalzahlen und negative Werte für den Prüf- und den Faktormodus. Die Primzahleigenschaft ist jedoch nur für ganze Zahlen sinnvoll, verwenden Sie also ganze Zahlen für verlässliche Ergebnisse. Das n-te-Primzahl-Feld akzeptiert nur positive ganze Zahlen.

Geprüft vom HandyTools-Hub-Team · Zuletzt aktualisiert