Alle Herausforderungen
Mittel 2 gelöst 28.6% Erfolgsquote

Largest Prime Factor

Find the largest prime that divides a positive integer.

Das lernst du

  • Divide out factors from smallest to largest
  • Stop at the square root of what is left
  • Handle large numbers efficiently

Problem

Übersetzung anzeigen

A prime is an integer greater than 1 with no positive divisors other than 1 and itself. Find the largest prime factor of n. When n is itself prime, return n.

Implement largest_prime_factor(n).

Input

n: The integer to factor.

Output

Return its largest prime divisor.

Einschränkungen

2 ≤ n ≤ 10¹². The input 1 is excluded because it has no prime factor.

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, so the largest prime factor is 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 is prime, so it is its own largest prime factor.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Remove small prime factors first; any remaining value can only shrink, and the last factor left is the answer.

Hinweis 2

Test divisors only up to the square root of the current remainder, and divide it out repeatedly when it fits.

Hinweis 3

If the remainder is still above 1 after checking smaller factors, that remainder is prime and is the largest factor.

Erwartete Komplexität

O(√n) time, O(1) extra space

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.