Divisor E Multiplo

Cálculo de divisor e múltiplo: o que funciona de verdade

A diferença entre divisor e múltiplo é simplesmente a direção da operação. Divisor divide o número alvo sem deixar resto. Múltiplo é o resultado de multiplicar o número alvo por qualquer inteiro. A maioria dos erros começa aí, na confusão de qual direção olhar. Para encontrar divisores de N, o método ingênuo é testar 1, 2, 3 até N e ver onde o resto é zero. Isso funciona para números pequenos, mas é impraticável para valores acima de dez mil. A otimização real é testar só até a raiz quadrada de N. Se i divide N, então N/i também é divisor. Isso corta o trabalho de 1.000.000 iterações para 1.000. A diferença é a mesma entre um script que roda em três segundos e um que trava seu terminal.

Múltiplos são trivialmente mais simples. Gera-se multiplicando N por 1, 2, 3, 4, e assim por diante. Não há limite prático, exceto o tamanho do tipo numérico que você está usando. Em Python, inteiros são arbitrários, então você pode gerar milhões de múltiplos sem estouro. Em C ou Java, um int de 32 bits estoura em 2.147.483.647. Múltiplos de 70mil já passam disso.

Métodos práticos de cálculo

O algoritmo de Euclides para o MDC (máximo divisor comum) é a ferramenta mais útil do dia a dia. A implementação recursiva é três linhas: se b for zero, retorne a; senão, chame a função com b e o resto de a dividido por b. Para calcular o MMC (mínimo múltiplo comum), use a relação MMC(a,b) = |a×b| / MDC(a,b). Isso evita gerar listas enormes de múltiplos e testar uma por uma, que é o método que todo mundo inventa na primeira vez. Decomposição em fatores primos é o caminho para números grandes. Se você precisa listar todos os divisores de 720, por exemplo, fatorar como 2 × 3² × 5¹ e usar a fórmula (4+1)(2+1)(1+1) = 30 divisores é muito mais rápido que testar 720 números. A partir dos fatores primos, gera-se todos os divisores combinando potências de cada fator. Funciona bem até números com cerca de 20 fatores primos distintos antes de a lista ficar intratável.

Problema real que encontrei no campo

Trabalhando com escalonamento de tarefas em lotes, precisei sincronizar dois ciclos com períodos de 86400 segundos e 3600 segundos. O MMC teórico era 86400, mas ao calcular com a fórmula do MDC, o produto 86400×3600 transbordava um int32 durante a multiplicação intermediária. A solução foi calcular primeiro a divisão: (86400 / MDC(86400,3600)) × 3600. Assim a operação intermediária nunca excede o maior número original. Esse padrão de dividir antes de multiplicar vale para qualquer par de números onde o produto dos dois exceda o limite do tipo. Outro caso que deu problema foi com números primos grandes em criptografia. Tentar fatorar um número de 12 dígitos por força bruta é viável em questão de segundos, mas a partir de 15 dígitos o tempo dispara para horas ou dias. Aí o algoritmo de Euclides não ajuda mais, porque ele só calcula MDC e MMC. Para fatoração pura de números grandes, sieve de Eratosthenes pré-computado ou o trial division otimizado com primos até N são as opções mais razoáveis sem recorrer a bibliotecas especializadas como Sympy ou GMP.

divisor e multiplo: onde as pessoas erram

O erro mais frequente é listar múltiplos quando pedem divisores, ou vice-versa. A verificação rápida é: se o resultado é menor ou igual ao número original, são divisores. Se é maior ou igual, são múltiplos. Número primo tem exatamente dois divisores: 1 e ele mesmo. Número composto tem mais que dois. 1 é um caso à parte: tem apenas um divisor, ele mesmo, e não é primo. Números negativos também causam confusão. Matematicamente, -12 tem divisores como -3, -4, -6, além dos positivos. Na prática, salvo em contextos teóricos, restringe-se aos divisores positivos. A mesma lógica se aplica ao MMC: oMMC pode ser definido como negativo, mas a convenção padrão usa o valor absoluto.

Um detalhe que ninguém menciona mas faz diferença: divisores de um quadrado perfeito aparecem em quantidade ímpar. Todos os outros números inteiros positivos têm quantidade par de divisores. Isso acontece porque os pares (i, N/i) se cancelam, exceto quando i = N/i, que ocorre apenas em quadrados perfeitos. Útil para verificação rápida em problemas competitivos.

Limitações que você precisa saber

O método de teste de divisão até N tem complexidade O(N). Para N = 10¹², isso dá 1.000.000 de operações. Sim, é viável, mas se você precisar fazer isso milhares de vezes em um loop, o tempo soma. Fatoração portrial division pré-computando primos até N com um sieve reduz o número de divisores testados, mas consome memória. Para N acima de 10¹, sieve não cabe mais na memória e fatores primos se tornam proibitivamente caros. Para múltiplos, o problema inverso também existe: gerar múltiplos de muitos números simultaneamente cria combinações exponenciais. O MMC de um conjunto grande de números pode crescer além de qualquer representação prática. Números com muitos fatores primos distintos são os piores casos. Um número com 15 fatores primos distintos já gera 2¹ = 32.768 divisores só para listar. A lista em si consome megabytes, e processá-la é outra coisa.

Quando o problema exige listar divisores de centenas de números diferentes, um sieve de divisores pré-computado é mais eficiente. Você inicializa um array onde cada posição contém uma lista vazia, e para cada i de 1 até N, adiciona i a todas as suas posições múltiplas. Complexidade O(N log N), mas o custo de memória é proporcional a N log N também. Para N = 10, isso exige alguns gigabytes. Viável em servidores, inviável em máquina local. Se você precisa apenas verificar se um número é divisor de outro, a operação de módulo (% em Python, % em C/Java) é suficiente e roda em tempo constante. Se precisa da lista completa, aí entra a decisão entre força bruta, fatoração, ou sieve, dependendo do tamanho e da frequência. Não existe solução única que domine todos os cenários. Escolha o método que cabe nos seus limites de tempo e memória, e teste com dados reais antes de confiar na teoria.