Primzahl-Rechner

Eine Primzahl ist eine ganze Zahl größer als eins mit genau zwei positiven Teilern: eins und der Zahl selbst. Zahlen größer als eins mit weiteren Teilern heißen zusammengesetzt. Sieben ist eine Primzahl, weil nur eins und sieben sie ohne Rest teilen. Neun ist zusammengesetzt, weil drei ein weiterer Teiler ist. Null und eins sind weder prim noch zusammengesetzt. Diese Festlegung bewahrt wichtige zahlentheoretische Ergebnisse und die Eindeutigkeit der Primfaktorzerlegung. Dieser Rechner prüft die Primalität, indem er nach einem Teiler sucht. Gerade Zahlen größer als zwei lassen sich sofort ausschließen. Bei einem ungeraden Kandidaten müssen nur ungerade Teiler bis zur Quadratwurzel geprüft werden. Ist eine zusammengesetzte Zahl gleich a mal b, muss mindestens einer der Faktoren höchstens so groß wie die Quadratwurzel sein. Andernfalls wären beide größer und ihr Produkt würde die Zahl übersteigen. Wird bis zu dieser Grenze kein Teiler gefunden, ist die Zahl nachweislich prim. Das Ergebnis zeigt außerdem die nächstkleinere und nächstgrößere Primzahl. Dazu werden aufeinanderfolgende ganze Zahlen nach außen hin geprüft, bis eine Primzahl erreicht ist. Zwei hat keine kleinere Primzahl, da sie die erste ist. Primzahllücken sind unterschiedlich: Manche Primzahlen liegen nur zwei auseinander und bilden Primzahlzwillinge, während andere Nachbarn viel größere Abstände haben. Oberhalb jeder gewählten ganzen Zahl gibt es stets noch eine Primzahl, wie Euklids klassischer Beweis der Unendlichkeit der Primzahlen zeigt. Primzahlen sind grundlegend für die Arithmetik, weil jede ganze Zahl größer als eins eindeutig in Primfaktoren zerlegt werden kann. Sie unterstützen das Kürzen von Brüchen, Verfahren zum größten gemeinsamen Teiler, modulare Arithmetik und viele Teilbarkeitsbeweise. Moderne Public-Key-Kryptografie nutzt Operationen mit großen Primzahlen und rechnerisch schwierigen Umkehrproblemen. Auch Hashtabellen, Randomisierungstechniken, Fehlerkorrekturcodes und zyklische Muster verwenden Primzahleigenschaften. Prüfe von Hand zunächst die Teilbarkeit durch zwei, drei und fünf und anschließend mögliche Primteiler bis zur Quadratwurzel. Teilbarkeitsregeln können das beschleunigen, doch die Probedivision bleibt für überschaubare Eingaben die zugrunde liegende Beweismethode. Der Rechner verwendet exakte ganzzahlige Restprüfungen statt statistischer Schätzungen. Deshalb ist jede Antwort im zulässigen Bereich deterministisch. JavaScript stellt gewöhnliche Ganzzahlen nur bis zur Grenze sicherer Ganzzahlen exakt dar, weshalb die Eingabe auf diesen Bereich beschränkt ist. Extrem große kryptografische Kandidaten benötigen spezielle Großzahlalgorithmen wie Miller-Rabin mit anschließenden stärkeren Beweisverfahren. Für Schulaufgaben, Faktorprüfungen, Folgenuntersuchungen und alltägliche Zahlentheorie ist die hier verwendete exakte Quadratwurzelmethode einfach und zuverlässig. Gib eine nichtnegative ganze Zahl ein, um ihre Einordnung und die nächsten Primzahlnachbarn zu sehen.