Fatoração de Números Primos

Como usar a Fatoração de Números Primos

1. 1Digite um número inteiro maior que 1. Pode ser primo ou composto.
2. 2Veja a fatoração completa. O resultado aparece automaticamente, sem precisar clicar em nada.

O que é fatoração em números primos

O Teorema Fundamental da Aritmética garante que todo número inteiro maior que 1 pode ser escrito como um produto único de números primos (números que só são divisíveis por 1 e por eles mesmos). Essa calculadora usa o método de divisão sucessiva: testa se o número é divisível por 2, depois por 3, 5, 7... até que sobre apenas 1 ou um fator primo maior.

Exemplo de código: fatoração por divisão sucessiva

function fatorar(n) {
  const fatores = [];
  let divisor = 2;
  while (n > 1) {
    while (n % divisor === 0) {
      fatores.push(divisor);
      n /= divisor;
    }
    if (divisor * divisor > n && n > 1) {
      fatores.push(n);
      break;
    }
    divisor++;
  }
  return fatores;
}

A fatoração em primos é a base de conceitos como o MDC e o MMC (calculáveis a partir dos fatores comuns entre dois números), a simplificação de frações, e — em escala muito maior — da segurança de algoritmos de criptografia como o RSA, que depende do fato de ser computacionalmente difícil fatorar números muito grandes formados pelo produto de dois primos.

Por que a divisão sucessiva funciona, mas não escala infinitamente

O algoritmo desta calculadora testa divisores em ordem crescente a partir de 2, e para de buscar assim que o divisor testado ultrapassa a raiz quadrada do que sobrou de n — nesse ponto, o que restou só pode ser 1 ou um único fator primo. Essa otimização (parar em √n em vez de testar até n) já reduz bastante o trabalho, mas para números com centenas de dígitos formados por dois primos grandes, mesmo essa versão otimizada se tornaria impraticavelmente lenta — é exatamente essa dificuldade computacional que sustenta a segurança do RSA.

Casos de teste sugeridos para uma implementação de fatoração

• Um número primo (o resultado deve ser só ele mesmo, sem quebrar em nenhum fator menor).
• Uma potência de 2 (ex.: 128 = 2⁷), que expõe se o loop interno de divisão repetida está correto.
• Um número que é produto de dois primos grandes e próximos entre si (ex.: 91 = 7 × 13), caso em que o algoritmo de divisão sucessiva demora mais, por precisar testar quase todos os divisores até a raiz quadrada.
• O número 4 (menor composto par), que confirma se o mesmo fator primo é listado múltiplas vezes quando necessário (4 = 2 × 2).

Perguntas Frequentes