GCD, LCM e algoritmo euclideo
Calcolare rapidamente e correttamente divisori e multipli
GCD, LCM e algoritmo euclideo è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 1 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.
Perché i divisori sono importanti
Moltissimi problemi delle gare di programmazione dipendono dai fattori comuni di due numeri. Lo strumento più utile in questo caso è il MCD, il massimo comune divisore. 🔢
Che cosa significa MCD
Il MCD di due interi è il numero più grande che divide entrambi senza resto. Per 12 e 18 è 6, perché 6 divide entrambi esattamente.
Il metodo lento
Potrebbe provare ogni numero partendo dal valore più piccolo e procedendo verso il basso finché non ne trova uno che divide entrambi. Funziona, ma è troppo lento per gli input grandi.
L'intuizione euclidea
L'algoritmo euclideo è il metodo veloce. L'idea fondamentale è che il MCD di a e b è uguale al MCD di b e del resto della divisione di a per b.
La ricorrenza
Ripeta il passaggio di scambio e modulo finché il resto non diventa zero. L'ultimo valore non nullo rimasto è la sua risposta, cioè il MCD stesso.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aScrivere il codice
Un breve ciclo continua a sostituire la coppia finché b non raggiunge zero. Richiede circa log passi, quindi è rapidissimo anche per numeri enormi.
def gcd(a, b):
while b:
a, b = b, a % b
return aUsare la libreria standard
Raramente è necessario implementarlo da zero. Python include math.gcd, che è corretto, veloce e gestisce autonomamente gli argomenti nulli.
from math import gcd
print(gcd(12, 18))Dal MCD all'MCM
L'MCM, il minimo comune multiplo, è il numero più piccolo divisibile per entrambi i valori. È direttamente collegato al MCD appena calcolato.
La formula dell'MCM
Moltiplichi i due numeri e poi divida per il loro MCD. Divida sempre prima per evitare l'overflow nei prodotti molto grandi.
def lcm(a, b):
return a // gcd(a, b) * bMCD di un'intera lista
Per calcolare il MCD di molti numeri, lo applichi a coppie in successione. In Python, reduce applica math.gcd da sinistra a destra agli elementi della lista.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Gestire il caso zero
Per definizione, gcd(a, 0) equivale ad a e gcd(0, 0) è 0. Conoscere questo caso limite impedisce ai cicli di comportarsi in modo errato con un input vuoto.
Verifica rapida
È il momento di verificare il passaggio euclideo fondamentale.
Riepilogo
Ora può calcolare il MCD con l'algoritmo euclideo in un numero logaritmico di passi, ricavare l'MCM e applicare entrambi a una lista. ✅
Domande Frequenti
La lezione «GCD, LCM e algoritmo euclideo» è gratuita?
Sì — il testo completo di «GCD, LCM e algoritmo euclideo» è 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 «GCD, LCM e algoritmo euclideo»?
Calcolare rapidamente e correttamente divisori e multipli 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 1 di 4.
Quanto tempo richiede la lezione «GCD, LCM e algoritmo euclideo»?
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