Fatoração Prima e Divisores
Decomponha N em potências de primos e conte os divisores.
Fatoração Prima e Divisores é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 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 Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Divida N em partes
Todo inteiro maior que 1 é um produto único de primos. Encontrar essa decomposição, sua fatoração em primos, abre caminho para muitos problemas de teoria dos números. 🧩
A ideia da divisão por tentativa
Extraia o menor primo que divide n, divida n por ele e repita. Essa simples divisão por tentativa reduz n até 1.
Percorra até a raiz
Teste os divisores i enquanto i*i permanecer menor ou igual a n. Depois da raiz quadrada, no máximo um fator primo pode permanecer.
while i * i <= n:
...Extraia cada fator
Enquanto i dividir n, continue dividindo e registre i. Isso captura toda a potência desse primo antes de prosseguir.
while n % i == 0:
factors.append(i)
n //= iO primo restante
Depois do laço, se n ainda for maior que 1, ele próprio será um fator primo maior que a raiz quadrada. Adicione-o uma vez.
if n > 1:
factors.append(n)A rotina completa
Juntas, essas etapas produzem a fatoração em tempo O(sqrt n), retornando cada primo com sua multiplicidade completa e na ordem correta.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fAgrupe em potências
Para contar divisores, você quer cada primo com seu expoente, como 2^3 em vez de 2,2,2. Um contador contabiliza as repetições de forma simples.
from collections import Counter
exp = Counter(factorize(n))A fórmula dos divisores
Se n for p1^a vezes p2^b, o número de divisores será (a+1) vezes (b+1). Cada expoente recebe uma opção adicional.
Conte os divisores
Multiplique um mais cada expoente considerando todos os primos. Isso fornece a contagem total de divisores sem precisar listá-los.
count = 1
for e in exp.values():
count *= (e + 1)Soma dos divisores
Uma fórmula relacionada soma os divisores usando a série geométrica de cada primo. Conhecê-la ajuda a resolver problemas sobre números perfeitos e alíquotas.
Velocidade com uma peneira
Para muitas fatorações, pré-calcule o menor fator primo de cada número usando uma peneira. Assim, cada consulta é fatorada em log n etapas.
Verificação rápida
Aplique a fórmula de contagem de divisores a um número concreto.
Revisão
Agora você pode fatorar N por divisão de tentativa em O(sqrt n), capturar o primo restante, agrupar os expoentes e contar os divisores com a fórmula do produto. ✅
Perguntas Frequentes
A aula “Fatoração Prima e Divisores” é grátis?
Sim — o texto completo de “Fatoração Prima e Divisores” é 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 Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Fatoração Prima e Divisores”?
Decomponha N em potências de primos e conte os divisores. Você pratica Coding Interview Prep 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 Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep 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 4 de 4.
Quanto tempo leva a aula “Fatoração Prima e Divisores”?
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 Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep 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