Um Número Natural Que Tem Mais Do Que 8 Divisores

Encontrando números com muitos divisores na prática

Quando você precisa trabalhar com um número natural que tem mais do que 8 divisores, a primeira coisa que a maioria das pessoas faz é começar a testar números um por um. Isso funciona para valores pequenos, mas rapidamente se torna exaustivo quando o número sobe acima de cem ou duzentos. O problema é que a contagem ingênua de divisores é basicamente um loop for que testa cada candidato até a raiz quadrada, e isso escala mal. A função d(n), também chamada tau(n) ou (n), conta quantos divisores positivos um inteiro n possui. O jeito certo de calcular isso é usando a fatoração prima. Se n = p^a × p^a × ... × p^a, então o número de divisores é (a + 1)(a + 1)...(a + 1). A desigualdade que importa aqui é simplesmente esse produto sendo maior que 8. Não tem mistério, mas tem uma pegadinha comum que todo mundo acaba cometendo na primeira vez. Os menores números que satisfazem essa condição são 24 (6 divisores na verdade — espere, deixa eu conferir: 1, 2, 3, 4, 6, 8, 12, 24. São exatamente 8. Não serve.), 30 (1, 2, 3, 5, 6, 10, 15, 30 — também 8, não serve), 36 (1, 2, 3, 4, 6, 9, 12, 18, 36 — 9 divisores, serve). Então o primeiro exemplo é 36. Depois vem 40 (8 divisores, não), 42 (8, não), 48 (1, 2, 3, 4, 6, 8, 12, 16, 24, 48 — 10 divisores, serve). E por aí vai.

Método prático para gerar e verificar

O método que eu uso no dia a dia é o seguinte. Fatoro o número em primos, aplico a fórmula do produto (a + 1), e comparo com 8. Para gerar candidatos eficientemente, eu monto números a partir de combinações de primos pequenos. A lógica é: para maximizar o número de divisores mantendo o valor do número baixo, você distribui os expoentes dos primos menores de forma decrescente. Pares como (2,1) para 2²×3¹ geram 6 divisores com n=12. Pares como (2,1,1) para 2²×3¹×5¹ geram 12 divisores com n=60. É basicamente o princípio dos números altamente abundantes, só que aplicado ao limiar de 8 divisores. Um detalhe que as tabelas comuns não mostram: números com exatamente 8 divisores são extremamente frequentes perto dos múltiplos de 60 e 84. Isso causa confusão porque todo mundo quer mais de 8, e o algoritmo ingênuo muitas vezes para no primeiro candidato que acha 8 divisores sem verificar se o próximo já passa disso. Eu levei dois dias tentando achar uma falha num script que eu tinha escrito porque ele retornava 72 como candidato válido, quando 72 na verdade tem 12 divisores e era perfeitamente correto — o problema era outro: o script estava classificando números como "inválidos" quando chegava a exatamente 8 e parava de incrementar o contador de forma consistente em casos de quadrados perfeitos. Quadrados perfeitos têm um divisor central (a raiz quadrada) que é contado uma única vez, e isso quebra a simetria aparente do loop de verificação.

Dica técnica sobre performance

Se você precisa processar muitos números de uma vez, pré-computar os valores de d(n) com um crivo é muito mais rápido do que fatorar cada candidato individualmente. Um crivo simples de Euler constrói o array tau em O(n log log n), e depois basta filtrar onde tau[i] > 8. Para n até 1 milhão, isso leva menos de 2 segundos em Python e roda uma única vez. Fatoração individual, pelo mesmo intervalo, leva minutos em vez de segundos. O contra-bônus é que o crivo consome memória proporcional ao intervalo. Se você precisa trabalhar com números acima de 10, o crivo não cabe na memória e volta para a fatoração. Nesse caso, trial division otimizada com uma tabela de primos até n é o suficiente para a maioria dos usos práticos, e o tempo médio por número fica na casa dos microssegundos quando o número já tem fatoração pequena.

Quando o método falha

O problema real aparece quando você precisa encontrar todos os números com exatamente k divisores em um intervalo enorme, tipo [1, 10¹²]. Nesse cenário, nem o crivo nem a fatoração individual valem a pena por si sós. A abordagem correta é gerar candidatos construindo combinações de expoentes primos de forma sistemática — basicamente um backtracking sobre partições do inteiro k. Para k = 9, as partições possíveis de 9 como produto de fatores maiores que 1 são 9 e 3×3, que correspondem a formas normais p e p²×p². Para k = 10: 10 e 5×2, ou seja p e p×p¹. Cada partição gera um conjunto de famílias de candidatos, e você enumerador essas famílias em vez de testar inteiros aleatórios. Eu descobri isso da forma mais difícil quando um cliente pediu para listar todos os números abaixo de 500 milhões com exatamente 16 divisores. O crivo direto daria cerca de 500 MB de RAM e levou uns 8 segundos na máquina dele. A enumeração por partições, com poda de árvore, rodou em 0,3 segundos e consumiu menos de 200 KB. A diferença é brutal. Resumindo: para números pequenos, o crivo funciona bem. Para intervalos médios, fatoração individual com trial division otimizada resolve. Para números grandes ou quando a contagem precisa ser precisa e rápida, a geração por partições de expoentes é o caminho. A regra de ouro é nunca usar o método errado para o tamanho do problema, porque cada um tem gargalos completamente diferentes.

Exemplo rápido de implementação

Um código mínimo em Python para verificar um único número seria algo como uma função que fatora em primos, calcula o produto dos expoentes mais um, e retorna verdadeiro se o resultado for maior que 8. Sem frescura. Se quiser rodar isso em lote, basta envolver num loop e trocar a estratégia de fatoração conforme o tamanho dos números. O importante é ter claro desde o início qual é o intervalo de trabalho, senão você gasta tempondo o método errado.