Numero di divisori tramite fattorizzazione in primi
Un approccio ingenuo per trovare il numero di multipli di un intero positivo n consiste nel ciclare su tutti i numeri da 1 a n (inclusi) e contare quanti di questi dividono n.
Tuttavia, questo metodo è molto lento. È possibile trovare il numero di divisori di n utilizzando i suoi fattori primi (poiché individuare i fattori primi richiede solo tempo pari a O(√n)).
Immagina un numero rappresentato come prodotto dei suoi fattori primi:
Possiamo calcolare il numero di divisori di n prendendo tutti gli esponenti, aggiungendo 1 a ciascuno e moltiplicando i risultati:
Questo può essere implementato in modo molto simile a come si trovano tutti i fattori primi di n:
n = ...
p, divisors = 1, 1 # fattore primo e numero di divisori
while p * p <= n: # finché p <= sqrt(n)
p += 1 # aggiunge 1 al fattore primo a ogni iterazione
if n % p != 0: # non fare nulla se n non è divisibile da p
continue
exp = 0 # contatore per l'esponente
while n % p == 0: # dividi tutte le volte possibili
n //= p
exp += 1
divisors *= exp + 1 # aggiorna il prodotto
if n > 1: # se p > sqrt(n) => n è un fattore primo a sé
divisors *= 2 # aggiunge n come divisore con esponente 1
print(divisors)Sfida: Trova il numero di divisori di n
Dato un intero n, devi trovare il numero dei divisori di n.
Ingresso
La prima riga dell’ingresso contiene un singolo intero n (2 ≤ n ≤ 10^9).
Uscita
Il programma deve stampare il numero di divisori di n.
Esempi
Ingresso | Uscita |
8 | 4 |
17 | 2 |
2048 | 12 |
48 | 10 |
Bonus: Perché sommando 1 a tutti gli esponenti e moltiplicando gli esponenti risultanti si ottiene il numero totale di divisori di n?
L’intuizione alla base della formula per determinare il numero di divisori di n deriva dal considerare il numero di combinazioni dei suoi fattori primi. L’esponente di ogni fattore indica quante volte si può utilizzare quel fattore nella moltiplicazione che dà come risultato un divisore di n. Aggiungere 1 a ciascun esponente permette di includere anche le combinazioni che prevedono 0 fattori primi (il che corrisponde a includere 1 e n stesso tra i divisori). Il risultato finale, ottenuto moltiplicando (esponente + 1) di ogni fattore primo, conta appunto tutte le possibili combinazioni di fattori e fornisce il numero totale di divisori di n.
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB