Problema
Un numero primo è un intero maggiore di 1 che non ha divisori positivi diversi da 1 e da sé stesso. Trova il massimo fattore primo di n. Se n è esso stesso primo, restituisci n.
Implementa largest_prime_factor(n).
Input
n: L'intero da fattorizzare.
Output
Restituisci il suo massimo divisore primo.
Vincoli
2 ≤ n ≤ 10¹². L'input 1 è escluso perché non ha fattori primi.
Esempi
Input:
n = 84
Output atteso:
expected = 7Input:
long long n = 84;
Output atteso:
long long expected = 7;Input:
long n = 84;
Output atteso:
long expected = 7;Spiegazione
84 = 2 × 2 × 3 × 7, quindi il massimo fattore primo è 7.
Input:
n = 13
Output atteso:
expected = 13Input:
long long n = 13;
Output atteso:
long long expected = 13;Input:
long n = 13;
Output atteso:
long expected = 13;Spiegazione
13 è un numero primo, quindi è il suo stesso massimo fattore primo.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Rimuovi prima i piccoli fattori primi; il valore rimanente può solo diminuire, e l’ultimo fattore rimasto è la risposta.
Suggerimento 2
Prova i divisori solo fino alla radice quadrata del resto corrente, e dividilo ripetutamente quando entra.
Suggerimento 3
Se dopo aver controllato i fattori minori il resto è ancora > 1, allora quel resto è primo ed è il fattore più grande.
Complessità attesa
tempo O(√n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.