Fator comum mais alto do Python (HCF / GCD)

Calcule o Maior Fator Comum (HCF) ou Máximo Divisor Comum (MDC) de dois números usando o algoritmo euclidiano.

Visão geral

O Maior Fator Comum (HCF), também conhecido como Máximo Divisor Comum (GCD), é o maior número inteiro positivo que divide dois ou mais números inteiros sem deixar resto.

O algoritmo euclidiano é um método extremamente eficiente para calcular o HCF. Afirma que o GCD de dois números também divide sua diferença.

Em Python, implementamos isso iterativamente usando um loop while onde substituímos continuamente o número maior pelo restante de sua divisão.

Saída de código e execução

Implementação de loop euclidiano para encontrar HCF/GCD de dois números.

hcf_gcd.py

Experimente no 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))

Saída terminal

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

Implementação passo a passo

Simplificação de frações e mecanismos matemáticos
Algoritmos de criptografia (como geração de chaves privadas RSA)
Projetando cronogramas de eventos periódicos

Perguntas frequentes

O Python tem uma função GCD integrada?

Sim! A biblioteca padrão do Python contém `math.gcd(a, b)` que usa uma implementação C compilada nos bastidores.

Tópicos Relacionados

Mínimo Múltiplo Comum (LCM) do Python

Encontre o mínimo múltiplo comum (LCM) de dois números usando sua relação HCF em Python.

Script de calculadora simples em Python

Construa uma calculadora básica em Python. Aprenda como mapear operadores matemáticos, usar fluxos de execução do usuário e lidar com a lógica de forma nativa.