Calculadora de MDC - Máximo divisor comum

O máximo divisor comum (GCF), também conhecido como máximo divisor comum (GCD) ou maior fator comum (HCF), é o maior inteiro positivo que divide cada um de um conjunto de inteiros sem deixar resto. Por exemplo, o GCF de 12 e 18 é 6, porque 6 é o maior número que divide exatamente 12 e 18. Os dois algoritmos mais comuns para calcular o GCF são o algoritmo de Euclides e a fatoração em primos. O algoritmo de Euclides é o mais eficiente dos dois para números grandes. Ele funciona substituindo repetidamente o par (a, b) por (b, a mod b) até que o resto seja 0; o último valor não zero de b é o GCF. O algoritmo executa O(log min(a,b)) passos, tornando-se extremamente rápido mesmo para inteiros muito grandes. A fatoração em primos calcula o GCF expressando cada número como um produto de primos elevados a potências e depois tomando o produto de cada primo elevado ao menor expoente encontrado em todos os números. Por exemplo, 12 = 2^2 * 3 e 18 = 2 * 3^2, então GCF(12, 18) = 2^1 * 3^1 = 6. Embora seja menos eficiente que o algoritmo de Euclides para números grandes, a fatoração em primos oferece uma visão pedagógica clara de por que o GCF é aquele valor. O GCF tem muitas aplicações práticas. Em aritmética, ele é usado para reduzir frações à forma mais simples: para simplificar a/b, divida numerador e denominador por GCF(a, b). Em geometria, o GCF de dois comprimentos fornece a régua mais longa que mede ambos sem resto. Em computação, o GCF aparece na aritmética modular, em algoritmos criptográficos (como a geração de chaves RSA) e na compressão de dados. Para mais de dois números, o GCF é calculado de forma iterativa. GCF(a, b, c) = GCF(GCF(a, b), c). Esta calculadora lida com qualquer quantidade de inteiros positivos e oferece tanto o algoritmo de Euclides (para resultados rápidos) quanto a fatoração em primos (para uma saída detalhada passo a passo). A visualização por fatoração em primos é especialmente útil para estudantes que estão aprendendo sobre fatores e divisibilidade.