Fattorizzazione in numeri primi

Qualsiasi intero positivo n ≥ 2 può essere rappresentato come prodotto di numeri primi:

Ci sono molte applicazioni utili nel trovare i fattori primi di un numero. Ad esempio, è possibile contare facilmente il numero dei divisori di quel numero, capire meglio il massimo comune divisore (GCD) e il minimo comune multiplo (LCM) tra due numeri, e così via.

Per rappresentare un numero n (ad esempio 300) come prodotto dei suoi fattori primi, si può partire dal più piccolo numero primo p (2) e, se n è divisibile, continuare a dividere n per p finché è possibile (300 / 2 = 150, 150 / 2 = 75).

Dopodiché si incrementa p di 1 (p = 3) e si prova a dividere n per il nuovo p. Se è possibile, si divide n per p finché è divisibile (75 / 3 = 25).

Poi si incrementa di nuovo p di 1 (p = 4) e si prova a dividere n per il nuovo p. Non è possibile dividere n per un numero che non sia primo, dato che n è stato prima diviso ripetutamente per numeri primi più piccoli. Nel nostro caso, 300 risulta divisibile per 4, ma 75 non lo è, poiché abbiamo già diviso 300 per 2 (che è un divisore di 4) più volte in precedenza. Quindi, poiché abbiamo “consumato” tutti i fattori 2, i numeri successivi come 4, 6, 8 o qualunque multiplo di 2 non divideranno più il nostro n. Dato che il procedimento procede dal valore più piccolo a quello più grande, possiamo essere certi di rimanere con numeri primi per dividere il numero rimanente.

Allo step successivo, incrementiamo di nuovo il divisore di 1 (p = 5) e proviamo a dividere n per il nuovo p (75 / 5 = 5, 5 / 5 = 1). Questo processo continua finché il divisore diventa maggiore di . Se si arriva a un punto in cui il divisore è più grande di ⇒ il numero n che rimane è esso stesso un numero primo e possiamo considerarlo come uno dei divisori nella nostra risposta finale.

Perciò, nell’esempio, 300 può essere rappresentato come .

n = ...                              # Rappresenta n come prodotto di numeri primi
p, divisors, powers = 1, [], []      # fattore primo, divisori e i relativi esponenti

while p * p <= n:                    # finché p <= sqrt(n)
    p += 1                           # incrementa p a ogni iterazione
    if n % p != 0:                   # nessuna azione se n non è divisibile da p
        continue
    
    divisors.append(p)               # n % p == 0 => aggiungi p come fattore primo
    powers.append(0)                 # l'esponente parte da 0
    while n % p == 0:                # dividi finché possibile
        n //= p
        powers[-1] += 1              # incrementa l'esponente a ogni divisione

if n > 1:                            # se p > sqrt(n) => n è un fattore primo
    divisors.append(n)
    powers.append(1)

print(list(zip(divisors, powers)))   # stampa i fattori e i relativi esponenti

A ogni iterazione dell’algoritmo, dividiamo il numero per il suo fattore primo se possibile, continuando a dividere simultaneamente e incrementando l’esponente a ogni passo.

Facciamo ora una simulazione dell’algoritmo su diversi numeri:

n = 24

p = 2, n = 24 (abbiamo incrementato p da 1 a 2 all’inizio del ciclo) n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 12, powers = [1] n //= 2 ⇒ n = 6, powers = [2] n //= 2 ⇒ n = 3, powers = [3]

p = 3, n = 3 ⇒ interrompi il ciclo while poiché p * p = 9 è maggiore di 3

n > 1 ⇒ divisors = [2, 3], powers = [3, 1]

n = 75

p = 2, n = 75

p = 3, n = 75 n % 3 == 0 ⇒ divisors = [3], powers = [0] n //= 3 ⇒ n = 25, powers = [1]

p = 4, n = 25

p = 5, n = 25 n % 5 == 0 ⇒ divisors = [3, 5], powers = [1, 0] n //= 5 ⇒ n = 5, powers = [1, 1] n //= 5 ⇒ n = 1, powers = [1, 2]

p * p > n ⇒ interrompi il ciclo while ⇒ divisors = [3, 5], powers = [1, 2]

n = 84

p = 2, n = 84 n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 42, powers = [1] n //= 2 ⇒ n = 21, powers = [2]

p = 3, n = 21 n % 3 == 0 ⇒ divisors = [2, 3], powers = [2, 0] n //= 3 ⇒ n = 7, powers = [2, 1]

p * p > n ⇒ interrompi il ciclo while

n > 1 ⇒ divisors = [2, 3, 7], powers = [2, 1, 1]

n = 31

p = 2, n = 31

p = 3, n = 31

p = 4, n = 31

p = 5, n = 31

p = 6, n = 31

p * p > n ⇒ interrompi il ciclo while

n > 1 ⇒ divisors = [31], powers = [1]

Sfida

Dato un intero n, il tuo compito è trovare il suo più grande fattore primo.

Input

La prima riga dell’input contiene un singolo intero n (2 ≤ n ≤ ).

Output

Il programma deve stampare il più grande fattore primo di n.

Esempi

Input	Output
8	2
24	3
75	5
31	31

Bonus: Perché non controlliamo soltanto i numeri primi?

Attualmente, la nostra implementazione dell’algoritmo scorre tutti i numeri 2, 3, 4, … fino a . Potrebbe sembrare più ragionevole iterare soltanto sui numeri primi.

A prima vista sembra una buona idea (e in alcuni problemi potrebbe funzionare). Tuttavia, il processo per trovare tutti i numeri primi fino a richiederebbe più passaggi rispetto a iterare semplicemente da 2 a (più precisamente ). Quindi, individuare i numeri primi fino al limite richiesto sarebbe più costoso in termini di tempo rispetto ad attraversare tutti i numeri possibili fino a e controllare se n ne è divisibile.

Riesci a pensare a uno scenario in cui determinare i numeri primi in anticipo e iterare su di essi per trovare i fattori primi potrebbe invece risultare più efficiente?

Sfida

Input

Output

Esempi

Constraints

To check your solution you need to sign in

Sign in to continue