Alle Herausforderungen
Mittel 2 gelöst 28.6% Erfolgsquote

Größter Primfaktor

Finde die größte Primzahl, die einen positiven Integer teilt.

Das lernst du

  • Faktoren vom kleinsten zum größten herausteilen
  • Bei der Quadratwurzel des Rests aufhören
  • Große Zahlen effizient behandeln

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

Beispiel 1
Eingabe:
n = 84

Erwartete Ausgabe:
expected = 7
Eingabe:
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.

Beispiel 2
Eingabe:
n = 13

Erwartete Ausgabe:
expected = 13
Eingabe:
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 949 ms - 4/5 Code ansehen
2 KKKaneki Ken Python 1,000 ms - 3/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 2 vollständige Lösungen unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.