Fatoração em Números Primos
Decomponha um número inteiro nos fatores primos dele, liste os divisores e veja se ele é primo.
Roda inteiramente no seu navegador. Nada é enviado, registrado ou armazenado.
Fatoração em primos
2^3 × 3^2 × 5
- Ele é primo?
- não
- Fatores primos distintos
- 3
- Quantos divisores
- 24
- Divisores
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
Todo número inteiro acima de 1 é um produto de primos, e existe apenas um produto assim para ele — é o teorema fundamental da aritmética. Isto o encontra, e tudo o que decorre dele: quantos divisores o número tem e quais são.
Como funciona
Divisão por tentativa, com um atalho: depois de tirar o 2 e o 3, todo primo restante fica de um lado ou do outro de um múltiplo de seis, então os candidatos avançam de seis em seis em vez de dois em dois. O que sobreviver ao crivo é primo e entra como último fator.
Os divisores são construídos a partir da fatoração, e não testando todo número até n. Um número escrito como 2³ × 3² × 5 tem (3+1) × (2+1) × (1+1) = 24 divisores, e cada um é uma escolha de quantos de cada primo tomar — então listá-los não custa nada depois que a fatoração é conhecida.
O teto é um trilhão. A divisão por tentativa vai no máximo até a raiz quadrada do número, o que ali dá um milhão de passos — rápido. Acima disso, um número que por acaso fosse o produto de dois primos grandes deixaria a página carregando por um minuto, então ela recusa.
Exemplos
| Caso | Entrada | Resultado |
|---|---|---|
| Um número com muitos divisores | 360 | 2³ × 3² × 5 — 24 divisores |
| Um primo | 97 | 97 — primo, 2 divisores |
| Uma potência de dois | 1024 | 2¹⁰ — 11 divisores |
Perguntas frequentes
Por que ele começa em 2 e não em 1?
Porque 1 não tem fatoração em primos, e chamá-lo de primo quebraria a unicidade sobre a qual todo o assunto se apoia: se 1 fosse primo, 6 seria 2 × 3, e 1 × 2 × 3, e 1 × 1 × 2 × 3, e deixaria de haver uma resposta. O zero é pior ainda — todo número o divide.
Quantos divisores um número tem?
Some um a cada expoente da fatoração e multiplique. 360 é 2³ × 3² × 5, então 4 × 3 × 2 = 24. Um primo tem 2 — ele mesmo e 1 — e um quadrado perfeito sempre tem um número ímpar deles, porque um dos divisores é par de si mesmo.
Por que existe um teto?
A divisão por tentativa é exata e rápida até deixar de ser. O pior caso é um produto de dois primos perto da raiz quadrada, e o limite aqui está onde esse caso ainda responde dentro do carregamento de uma página. Uma recusa diz o que aconteceu; um tempo esgotado não diz nada.
É assim que se quebram chaves de criptografia?
Não, e esse é justamente o ponto. O RSA se apoia na dificuldade de fatorar um número de algumas centenas de dígitos; divisão por tentativa em um deles duraria mais que o universo. Os métodos melhores existem e continuam longe de bastar, e é por isso que o esquema funciona.
Bom saber
- Os divisores são listados por inteiro até sessenta e quatro deles; acima disso só a contagem aparece, porque uma página com novecentos números não é algo que alguém leia.
Todas as ferramentas de Matemática