Problem
Eine Primzahl ist eine ganze Zahl größer als 1, die keine positiven Teiler außer 1 und sich selbst hat. Finde den größten Primfaktor von n. Wenn n selbst eine Primzahl ist, gib n zurück.
Implementiere largest_prime_factor(n).
Eingabe
n: Die zu faktorisierende ganze Zahl.
Ausgabe
Gib ihren größten Primteiler zurück.
Einschränkungen
2 ≤ n ≤ 10¹². Die Eingabe 1 ist ausgeschlossen, da sie keinen Primfaktor besitzt.
Beispiele
Eingabe:
n = 84
Erwartete Ausgabe:
expected = 7Eingabe:
long long n = 84;
Erwartete Ausgabe:
long long expected = 7;Eingabe:
long n = 84;
Erwartete Ausgabe:
long expected = 7;Erläuterung
84 = 2 × 2 × 3 × 7, daher ist der größte Primfaktor 7.
Eingabe:
n = 13
Erwartete Ausgabe:
expected = 13Eingabe:
long long n = 13;
Erwartete Ausgabe:
long long expected = 13;Eingabe:
long n = 13;
Erwartete Ausgabe:
long expected = 13;Erläuterung
13 ist eine Primzahl und somit ihr eigener größter Primfaktor.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Entferne zuerst kleine Primfaktoren; jeder verbleibende Wert kann nur kleiner werden, und der letzte Faktor ist die Antwort.
Hinweis 2
Teste Teiler nur bis zur Quadratwurzel des aktuellen Rests und teile ihn wiederholt heraus, wenn er passt.
Hinweis 3
Ist der Rest nach den kleineren Faktoren noch größer als 1, dann ist dieser Rest prim und der größte Faktor.
Erwartete Komplexität
Zeit O(√n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.