Algoritmo de Euclides
Para 1071 e 462 o máximo divisor comum é 21, obtido em três divisões: 1071 = 462 × 2 + 147, depois 462 = 147 × 3 + 21 e por fim resto zero. Digite dois inteiros e veja cada passo, não só o resultado. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- A
- 1.071
- B
- 462
- Gcd
- 21
- Número de etapas
- 3
A calculadora do algoritmo de Euclides recebe dois inteiros e calcula o máximo divisor comum da forma como Euclides descreveu há mais de dois mil anos: dividindo repetidamente e guardando o resto. Em vez de retornar apenas o número final, ela retorna a lista completa de passos — cada linha da forma dividendo = divisor × quociente + resto — para que você veja exatamente como a resposta foi alcançada. Aceita valores negativos (o MDC usa valores absolutos), rejeita entradas não inteiras e recusa o caso indefinido mdc(0,0).
O que o algoritmo de Euclides realmente faz
O máximo divisor comum de dois inteiros é o maior número que divide ambos sem deixar resto. O algoritmo de Euclides o encontra sem fatorar nada, e é por isso que continua rápido mesmo com entradas muito grandes. A ideia é simples: se um número divide tanto a quanto b, também divide o resto da divisão de a por b.
Então você substitui o par (a, b) por (b, a mod b) e repete. Cada passo é uma divisão longa — por exemplo, 1071 = 462 × 2 + 147 — e você continua até o resto ser zero. O último resto diferente de zero é o MDC.
Como o resto diminui estritamente a cada passo, o laço sempre termina, e termina rápido: o número de passos é proporcional ao logaritmo da menor entrada.
Entradas, casos extremos e como os erros são relatados
Você envia dois campos, a e b, e ambos devem ser inteiros. Inteiros negativos são válidos: o MDC é definido sobre valores absolutos, então mdc(-1071, 462) é o mesmo que mdc(1071, 462), e a lista de passos é calculada sobre os valores absolutos. Zero é uma entrada válida para um dos campos — mdc(a, 0) é |a| e, nesse caso, a lista de passos fica vazia porque nenhuma divisão é necessária —, mas os dois campos iguais a zero são rejeitados, porque mdc(0,0) é matematicamente indefinido.
Erros nunca produzem resposta parcial: a requisição é recusada com um código legível por máquina e uma mensagem que você pode mostrar ao usuário.
Onde um MDC passo a passo faz diferença
O MDC puro é uma commodity — toda linguagem tem um na biblioteca padrão. O que esta capacidade acrescenta é o rastro. Professores e estudantes usam a lista de passos para verificar que um exercício foi resolvido com o verdadeiro algoritmo de Euclides, e não adivinhando divisores.
Desenvolvedores a usam ao depurar simplificação de frações, redução de proporções de aspecto ou verificações de coprimalidade, porque ver 252 = 105 × 2 + 42 aponta exatamente onde um cálculo manual divergiu do código. Quem estuda criptografia encontra o algoritmo como base da versão estendida que produz os coeficientes de Bézout e os inversos modulares; ver primeiro os passos simples da divisão torna esse salto muito mais fácil.
Casos de uso
Conferir um exercício resolvido
Cole os dois números de um problema de lição de casa e compare seus passos de divisão escritos com os que o algoritmo realmente produz.
Simplificar frações e proporções
Obtenha o MDC de um numerador e um denominador para reduzir uma fração, com a lista de passos como trilha de auditoria de como o divisor foi encontrado.
Ensinar o algoritmo antes da versão estendida
Mostre primeiro aos estudantes o rastro simples das divisões e depois avance para os coeficientes de Bézout e os inversos modulares construídos sobre o mesmo laço.
Perguntas frequentes
Quanto custa?
Também é grátis executar no seu navegador nesta página.
Por que mdc(0,0) é rejeitado?
Porque o máximo divisor comum de zero e zero é indefinido — todo inteiro divide zero, então não existe um que seja o maior. Forneça pelo menos um valor diferente de zero.
Posso passar números negativos?
Sim. O MDC é calculado sobre valores absolutos, então mdc(-1071, 462) retorna o mesmo resultado que mdc(1071, 462).
O que o array steps contém?
Um objeto por divisão: dividendo, divisor, quociente e resto, de modo que cada linha se lê dividendo = divisor × quociente + resto. O último resto diferente de zero é o MDC.
Quão grandes as entradas podem ser?
Até o inteiro seguro máximo, 9007199254740991, de modo que cada quociente e cada resto da saída é exato.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
curl -X POST https://api.kit.forhosting.com/math/euclidean-algorithm \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":1071,"b":462}'const res = await fetch("https://api.kit.forhosting.com/math/euclidean-algorithm", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 1071,
"b": 462
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/euclidean-algorithm",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 1071,
"b": 462
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/euclidean-algorithm", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":1071,"b":462}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":1071,"b":462}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/euclidean-algorithm", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Exemplo de requisição
{
"a": 1071,
"b": 462
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.euclidean_algorithm",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Limites
max_abs | 9007199254740991 |
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
O mesmo código roda grátis no seu navegador nesta página e também pela API paga.
O que o algoritmo de Euclides realmente faz
Este endpoint executa exatamente esse procedimento e devolve cada divisão feita, não apenas a conclusão, o que o torna útil tanto para conferir lição de casa quanto para auditar um cálculo dentro de um sistema maior.
Entradas, casos extremos e como os erros são relatados
Strings numéricas que representam inteiros exatos, como "1071", são aceitas; decimais, frações, notação científica e valores não numéricos são rejeitados com um erro invalid_input que explica o que houve de errado. Os valores são limitados pelo intervalo de inteiros seguros dos doubles IEEE 754, cerca de 9 quatrilhões, de modo que cada quociente e cada resto da saída é exato.
Perguntas técnicas
O que conta como inteiro?
Um número JSON sem parte fracionária, ou uma string de dígitos com sinal inicial opcional. Decimais, notação científica e valores não numéricos são rejeitados com um erro invalid_input.