Algoritmi Python

Massimo comun divisore con l'algoritmo di Euclide in Python

In questa lezione troverai il massimo comun divisore (MCD) di due numeri con l'algoritmo di Euclide.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

Introduzione

Il problema

Semplificare frazioni, dividere cose in gruppi uguali e molti rompicapi richiedono il numero più grande che divide due numeri. Provare tutti i candidati è lento con numeri grandi. Più di 2.000 anni fa Euclide trovò un metodo molto più veloce.

Immaginalo così

Il metodo di Euclide è come piastrellare un rettangolo con le piastrelle quadrate più grandi possibili. Ritagli il quadrato più grande che puoi da un rettangolo 48 × 18, poi da ciò che resta, e continui. Quando i pezzi combaciano esattamente senza avanzi, il lato dell'ultimo quadrato è la risposta.

Dal ritagliare quadrati al codice
first, second▭ Il rettangolo: 48 × 18
first % second✂️ Ciò che resta dopo aver ritagliato quadrati del lato più piccolo
first, second = second, first % second🔁 Ripeti con il pezzo avanzato
while second:✅ Non avanza niente: il lato è l'MCD, 6
gcd(a, b) = gcd(b, a % b) finché il resto è 0.
In una frase

Il massimo comun divisore (MCD) di due interi è il più grande intero positivo che li divide entrambi. L'algoritmo di Euclide lo trova sostituendo la coppia (a, b) con (b, a % b) finché b è 0.

Punti chiave

  1. first, second = second, first % second sostituisce la coppia con il numero più piccolo e il resto.
  2. Per 48 e 18 le coppie sono (48, 18), (18, 12), (12, 6), (6, 0).
  3. while second: si ferma quando il resto diventa 0.
  4. return abs(first) dà un risultato positivo anche per input negativi.

Quando si usa?

  • Semplificare frazioni e rapporti.
  • Trovare il minimo comune multiplo: a * b // gcd(a, b).
  • Rompicapi con i numeri, aritmetica modulare e basi della crittografia.

Quando non serve

  • Codice vero: math.gcd è già incluso in Python e nelle versioni recenti accetta un numero qualsiasi di argomenti.
  • Trovare tutti i divisori comuni: l'MCD dà solo il più grande.

Codice di esempio

Esegui codice →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
Crea un pulsante Run per questo esempio

Risultato dell'esecuzione

6

Spiegazione del codice

A ogni passo, la coppia (first, second) viene sostituita da (second, first % second). Quando il resto arriva a 0, il valore rimasto in first è il MCD, quindi il MCD di 48 e 18 è 6. La funzione abs() garantisce che il risultato sia sempre positivo. Il numero di passi cresce molto lentamente con la grandezza dei numeri, circa O(log n).

Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.

Esercizi di approfondimento

Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Usare la sottrazione invece del resto

Sottrarre ripetutamente dà la stessa risposta, ma è molto lento quando i due numeri sono molto diversi.

Problema
while first != second:
    if first > second:
        first -= second
    else:
        second -= first
Correzione
while second:
    first, second = second, first % second

Hai finito questa lezione?

Segnala come imparata per tenere traccia dei tuoi progressi.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide