GCD, LCM e o Algoritmo de Euclides
Calcule divisores de forma rápida e correta.
GCD, LCM e o Algoritmo de Euclides é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Por que os divisores são importantes
Muitos problemas de competições dependem de fatores compartilhados por dois números. A ferramenta mais útil aqui é o GCD, o máximo divisor comum. 🔢
O que significa GCD
O GCD de dois inteiros é o maior número que divide ambos sem resto. Para 12 e 18, ele é 6, pois 6 divide os dois exatamente.
A maneira lenta
Você poderia testar todos os números, começando pelo menor valor e descendo, até encontrar um que divida ambos. Funciona, mas é lento demais para entradas grandes.
A ideia euclidiana
O algoritmo euclidiano é a maneira rápida. A ideia principal é: o GCD de a e b é igual ao GCD de b e do resto da divisão de a por b.
A recorrência
Repita a etapa de troca e módulo até que o resto chegue a zero. O último valor não nulo restante é a sua resposta, o próprio GCD.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aImplemente você mesmo
Um laço curto continua substituindo o par até que b chegue a zero. Isso executa em cerca de log etapas, com enorme rapidez mesmo para números muito grandes.
def gcd(a, b):
while b:
a, b = b, a % b
return aUse a biblioteca padrão
Raramente é necessário implementar isso manualmente. O Python oferece math.gcd, que é correto, rápido e lida com argumentos nulos para você.
from math import gcd
print(gcd(12, 18))Do GCD ao LCM
O LCM, o mínimo múltiplo comum, é o menor número que é divisível pelos dois valores. Ele se relaciona diretamente ao GCD que você acabou de calcular.
A fórmula do LCM
Multiplique os dois números e depois divida pelo GCD. Sempre divida primeiro para evitar excesso de capacidade em produtos muito grandes.
def lcm(a, b):
return a // gcd(a, b) * bGCD de uma lista inteira
Para aplicar o GCD a muitos números, encadeie-o aos pares. A função de redução do Python aplica math.gcd da esquerda para a direita sobre a lista.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Trate o caso do zero
Por definição, gcd(a, 0) é igual a a, e gcd(0, 0) é 0. Conhecer esse caso-limite impede que seus laços se comportem mal com uma entrada vazia.
Verificação rápida
É hora de confirmar a etapa euclidiana principal.
Recapitulação
Agora você consegue calcular o GCD com o algoritmo euclidiano em etapas logarítmicas, derivar o LCM a partir dele e aplicá-los a uma lista. ✅
Perguntas Frequentes
A aula “GCD, LCM e o Algoritmo de Euclides” é grátis?
Sim — o texto completo de “GCD, LCM e o Algoritmo de Euclides” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “GCD, LCM e o Algoritmo de Euclides”?
Calcule divisores de forma rápida e correta. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “GCD, LCM e o Algoritmo de Euclides”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- GCD, LCM e o Algoritmo de Euclides
- Teste de Primalidade até sqrt(n)
- Crivo de Eratóstenes
- Fatoração Prima e Divisores