Kleinster Primfaktor

Der kleinste Primfaktor einer ganzen Zahl ist die kleinste Primzahl, die sie genau teilt. Bei einer Primzahl ist dieser Faktor die Zahl selbst; bei einer zusammengesetzten Zahl ist er die erste Primzahl ihrer Zerlegung und das günstigste Zertifikat, dass der Wert nicht prim ist.

Was der kleinste Primfaktor ist und was dieses Werkzeug liefert

Jede ganze Zahl n größer als eins hat nach dem Fundamentalsatz der Arithmetik eine eindeutige Multimenge von Primfaktoren, und unter diesen Primzahlen gibt es stets eine kleinste. Dieser Wert heißt kleinster Primfaktor, oft abgekürzt SPF in zahlentheoretischen Tabellen und Programmierwettbewerbsaufgaben. Ist n prim, ist der SPF n; ist n gerade, ist der SPF stets zwei; ist n Produkt größerer Primzahlen, ist der SPF die erste Primzahl, die n bei geordneter Probe teilt.

Diese Fähigkeit beantwortet nur diese Frage: sie listet nicht jede Primpotenz, berechnet nicht die Eulersche Phi-Funktion und stellt keine Primzertifikate für mehrtausendbitige Ganzzahlen aus.

Wie der deterministische Probealgorithmus funktioniert

Die Engine prüft zuerst die Teilbarkeit durch zwei und drei, weil gerade und dreifache Vielfache den Alltagseingaben dominieren und in konstanter Zeit gelöst werden. Verbleibende Kandidaten laufen ein Sechserschritt-Rad der Form 6k±1 ab fünf, das jede durch zwei oder drei teilbare ganze Zahl überspringt und dennoch jede Primzahl trifft. Sobald ein Kandidat n teilt, wird er als kleinster Primfaktor zurückgegeben — keine weitere Suche ist nötig, weil Kandidaten in aufsteigender Reihenfolge geprüft werden.

Erreicht die Schleife die ganzzahlige Quadratwurzel von n ohne Teiler, muss n prim sein und wird als eigener kleinster Primfaktor zurückgegeben. Die gesamte Arithmetik nutzt intern BigInt im veröffentlichten sicheren Ganzzahlbereich, damit Zwischenprodukte exakt bleiben; Ergebnisse werden dann als gewöhnliche JavaScript-Zahlen serialisiert. Die Worst-Case-Arbeit ist proportional zur Wurzel von n für Primzahlen und Semiprime mit großen Faktoren, akzeptabel für Unterrichtswerte und sichere-Ganzzahl-Komposita; für die vollständige Faktorisierung riesiger Ganzzahlen nutzen Sie eine eigene Faktorisierungsfähigkeit statt dieses Endpunkts für den kleinsten Faktor.

Wo ein Rechner für den kleinsten Primfaktor in reale Abläufe passt

Schülerinnen, Schüler und Lehrkräfte nutzen einen Rechner für den kleinsten Primfaktor, um Hausaufgaben zu prüfen, zu zeigen, warum eine Zahl eine Primbehauptung scheitert, indem die erste blockierende Primzahl genannt wird, und Intuition vor der vollständigen Faktorisierung aufzubauen. Anwendungsentwickler rufen ihn auf, wenn eine Pipeline nur den kleinsten Faktor braucht — etwa um Geradzahligkeit abzuschälen, für eine Pollard-artige Probe vor schwereren Methoden oder um offenkundig zusammengesetzte Konfigurationswerte mit einer konkreten Primzahl statt eines bloßen false abzulehnen.

Dateningenieure filtern numerische Spalten, die primförmig sein sollen: jeder Wert, dessen SPF kleiner als der Wert selbst ist, ist zusammengesetzt, und der Faktor landet im Audit-Protokoll ohne die volle Faktorliste zu expandieren. Wettbewerbs-Solver und Bildungs-APIs stellen SPF als ersten Baustein zu Omega-Zählungen, Radikalen und Siebtabellen bereit. Bevorzugen Sie dieses Werkzeug, wenn die Suchintention streng «was ist der kleinste Primfaktor von n?»

lautet — nicht wenn Sie jede Primpotenz, Primzertifikate für riesige multipräzise Ganzzahlen oder probabilistische Tests mit eigenen Zeugenlisten brauchen.