Fattore comune massimo di Python (HCF / GCD)

Calcola il massimo comun divisore (HCF) o il massimo comun divisore (MCD) di due numeri utilizzando l'algoritmo euclideo.

Prova nell'editor

Panoramica

Il massimo comune divisore (HCF), noto anche come massimo comune divisore (GCD), è il più grande intero positivo che divide due o più numeri interi senza lasciare resto.

L'algoritmo euclideo è un metodo estremamente efficiente per calcolare l'HCF. Afferma che il MCD di due numeri divide anche la loro differenza.

In Python, lo implementiamo in modo iterativo utilizzando un ciclo while in cui sostituiamo continuamente il numero più grande con il resto della sua divisione.

Codice e output di esecuzione

Implementazione del ciclo euclideo per trovare HCF/MCD di due numeri.

hcf_gcd.py

Prova nell'editor

def find_gcd(a, b):
    # Euclidean Algorithm
    while b != 0:
        a, b = b, a % b
    return a

print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))

Uscita terminale

GCD of 36 and 60 is: 12
GCD of 17 and 5 is:  1

Implementazione passo dopo passo

Semplificazione delle frazioni e motori matematici
Algoritmi di crittografia (come la generazione di chiavi private RSA)
Progettazione di palinsesti periodici di eventi

Domande frequenti

Python ha una funzione GCD incorporata?

Sì! La libreria standard di Python contiene `math.gcd(a, b)` che utilizza un'implementazione C compilata sotto il cofano.

Argomenti correlati

Python minimo comune multiplo (LCM)

Trova il minimo comune multiplo (LCM) di due numeri usando la loro relazione HCF in Python.

Script per calcolatrice semplice Python

Costruisci una calcolatrice di base in Python. Scopri come mappare gli operatori matematici, gestire i flussi di esecuzione degli utenti e gestire la logica in modo nativo.