Quadratfreie Zahl online prüfen

Eine quadratfreie Zahl enthält keinen Primfaktor zum Quadrat: In ihrer Primfaktorzerlegung kommt jede Primzahl höchstens einmal vor. Dieses Werkzeug liefert für jede positive ganze Zahl innerhalb der veröffentlichten Grenze eine eindeutige Antwort. Ist die Zahl nicht quadratfrei, wird außerdem eine Primzahl angegeben, deren Quadrat die Eingabe teilt. Damit erhalten Sie eine kurze und überprüfbare Begründung. Die Berechnung ist deterministisch, benötigt keinen Netzwerkzugriff und behandelt 1 gemäß der üblichen mathematischen Definition als quadratfrei.

Was quadratfrei bedeutet

Eine positive ganze Zahl ist quadratfrei, wenn keine Primzahl sie mehr als einmal teilt. Gleichbedeutend damit darf es keine Primzahl p geben, für die p zum Quadrat die ganze Zahl teilt. Beispielsweise ist 30 quadratfrei, denn ihre Primfaktorzerlegung lautet 2 × 3 × 5 und jede Primzahl tritt genau einmal auf.

Die Zahl 12 ist dagegen nicht quadratfrei, weil ihre Zerlegung 2² × 3 lautet und sie somit durch das Quadrat von 2 teilbar ist. Die Zahl 1 ist ein wichtiger Grenzfall: Ihre Primfaktorzerlegung ist leer, sie enthält also keine wiederholte Primzahl und gilt daher als quadratfrei. Das Werkzeug setzt diese Definition unmittelbar um.

Das Ergebnis enthält den ursprünglichen Wert und den booleschen Wert squarefree. Mit diesem Zeugen können Sie die Antwort leicht kontrollieren: Quadrieren Sie die angegebene Primzahl und teilen Sie die ursprüngliche Zahl durch das Ergebnis. Ein ganzzahliger Quotient belegt, weshalb die Eingabe die Prüfung nicht besteht, ohne dass dafür die vollständige Primfaktorzerlegung ermittelt werden muss.

So wird die Prüfung durchgeführt

Der Algorithmus verwendet exakte Ganzzahlarithmetik und eine begrenzte Probedivision. Er beginnt mit dem kleinsten möglichen Primfaktor und untersucht die möglichen Faktoren in aufsteigender Reihenfolge. Sobald ein Kandidat den verbleibenden Wert teilt, entfernt der Algorithmus ein Exemplar und prüft sofort, ob derselbe Kandidat den Rest erneut teilt.

Eine zweite Division bedeutet, dass das Quadrat des Kandidaten die ursprüngliche Eingabe teilt. Damit steht fest, dass die Zahl nicht quadratfrei ist, und die Berechnung kann enden. Kommt der Faktor nur einmal vor, wird die Suche mit dem verkleinerten Rest fortgesetzt.

Kandidaten oberhalb der Quadratwurzel dieses Rests müssen nicht getestet werden: Jeder zusammengesetzte Rest besitzt einen Faktor, der höchstens so groß wie seine Quadratwurzel ist, während ein am Ende verbleibender größerer Rest selbst genau ein Primfaktor ist. Das Verfahren stützt sich weder auf probabilistische Primzahltests noch auf zwischengespeicherte Tabellen, externe Dienste oder Gleitkommanäherungen. Die veröffentlichte Obergrenze hält den Aufwand vorhersehbar.

Die Prüfung auf sichere JavaScript-Ganzzahlen stellt zudem sicher, dass jede Division und jeder Rest die eingegebene Zahl exakt abbildet.

Eingabe und Ergebnis richtig verwenden

Geben Sie n als positive ganze Zahl ein, nicht als Dezimalzahl, Bruch, Zeichenfolge in wissenschaftlicher Schreibweise oder formatierte Zahl mit Trennzeichen. Werte unter 1 werden abgewiesen, weil diese Fähigkeit der üblichen Definition für positive ganze Zahlen folgt. Auch Werte über dem dokumentierten Höchstwert werden abgewiesen, damit die Laufzeit begrenzt bleibt.

Ein wahrer squarefree-Wert besagt, dass die ganze Zahl keinen quadrierten Primfaktor enthält; er besagt nicht, dass die Zahl eine Primzahl ist. Zahlen wie 6, 30 und 42 sind zusammengesetzt und dennoch quadratfrei, weil jeder ihrer verschiedenen Primfaktoren genau einmal vorkommt. Die Eingabe kann weitere wiederholte Primfaktoren enthalten, die nicht aufgeführt werden, denn ein einziger Zeuge genügt für die Entscheidung.

Die Ausgabe eignet sich für Validierungsregeln, zahlentheoretische Untersuchungen und Verarbeitungsschritte, die lediglich diese Klassifizierung benötigen. Der Algorithmus übermittelt die Eingabe an keinen Drittanbieter.