Fattorizzazione prima e divisori
Scomporre N in potenze prime e contare i divisori
Fattorizzazione prima e divisori è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Scomporre N
Ogni intero maggiore di 1 è un prodotto univoco di numeri primi. Trovare questa scomposizione, la sua scomposizione in fattori primi, permette di risolvere molti problemi di teoria dei numeri. 🧩
L'idea della divisione per tentativi
Estragga il più piccolo numero primo che divide n, lo elimini con una divisione e ripeta. Questa semplice divisione per tentativi riduce n fino a 1.
Iterare fino alla radice
Verifichi i divisori i finché i*i rimane minore o uguale a n. Oltre la radice quadrata, può rimanere al massimo un fattore primo.
while i * i <= n:
...Estrarre ogni fattore
Finché i divide n, continui a dividere e registri i. In questo modo cattura l'intera potenza di quel primo prima di procedere.
while n % i == 0:
factors.append(i)
n //= iIl primo residuo
Dopo il ciclo, se n è ancora maggiore di 1, è esso stesso un fattore primo maggiore della radice quadrata. Lo aggiunga una volta.
if n > 1:
factors.append(n)La procedura completa
Insieme, questi passaggi producono la scomposizione in tempo O(sqrt n), restituendo ogni primo con la sua molteplicità completa e nell'ordine corretto.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fRaggruppare in potenze
Per contare i divisori, vuole ogni primo con il suo esponente, ad esempio 2^3 anziché 2,2,2. Un Counter conta le ripetizioni in modo ordinato.
from collections import Counter
exp = Counter(factorize(n))La formula dei divisori
Se n è p1^a per p2^b, il numero di divisori è (a+1) per (b+1). Ogni esponente offre una scelta in più.
Conteggio dei divisori
Moltiplicando uno più ciascun esponente relativo a tutti i numeri primi si ottiene il conteggio totale dei divisori senza doverli elencare.
count = 1
for e in exp.values():
count *= (e + 1)Somma dei divisori
Una formula correlata calcola la somma dei divisori usando la serie geometrica di ciascun primo. Conoscerla è utile per i problemi sui numeri perfetti e sui divisori aliquoti.
Velocizzare con un crivello
Per molte fattorizzazioni, precalcoli il più piccolo fattore primo di ogni numero usando un crivello. In questo modo, ogni query può essere fattorizzata in log n passaggi.
Verifica rapida
Applichi la formula del conteggio dei divisori a un numero concreto.
Riepilogo
Ora sa fattorizzare N per divisione di prova in O(sqrt n), individuare il primo residuo, raggruppare gli esponenti e contare i divisori con la formula del prodotto. ✅
Domande Frequenti
La lezione «Fattorizzazione prima e divisori» è gratuita?
Sì — il testo completo di «Fattorizzazione prima e divisori» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Fattorizzazione prima e divisori»?
Scomporre N in potenze prime e contare i divisori Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Fattorizzazione prima e divisori»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- GCD, LCM e algoritmo euclideo
- Test di primalità fino a sqrt(n)
- Crivello di Eratostene
- Fattorizzazione prima e divisori