Primo pequeno: 97
- Entrada
- 97
- Saída esperada
- primo (fatoração: 97)
Só é preciso testar divisores até 9, porque √97 ≈ 9,85; nenhum número de 2 a 9 divide 97 exatamente.
Carregando ferramenta… / Loading tool…
números primos e fatoração
Um número primo só tem dois divisores positivos, 1 e ele mesmo. Esta página mostra por que basta testar divisores até a raiz quadrada do número para decidir isso, qual teste a ferramenta realmente usa por baixo dos panos, e a armadilha clássica que engana testes de primalidade mais simples.
Só é preciso testar divisores até 9, porque √97 ≈ 9,85; nenhum número de 2 a 9 divide 97 exatamente.
221 parece um número aleatório qualquer, mas falha no teste de divisibilidade por 13 antes de chegar a √221 ≈ 14,87; sem calculadora, é fácil confundir com primo.
A divisão sucessiva testaria até 99 divisores ímpares (√9973 ≈ 99,86); é o tipo de número onde o custo O(√n) começa a pesar à mão, mas continua instantâneo pelo Miller-Rabin.
Um número primo é um inteiro maior que 1 que não tem divisores inteiros positivos além de 1 e de si mesmo. Os primeiros primos são 2, 3, 5, 7, 11, 13…
Não. A definição de primo exige exatamente dois divisores positivos distintos, 1 e ele mesmo; o número 1 só tem um divisor (ele mesmo), então fica numa categoria própria, nem primo nem composto, e a ferramenta marca esse caso separado do status "primo".
Sim, e é o único: todo outro número par é divisível por 2 além de por 1 e por si mesmo, o que já dá três divisores e desqualifica a primalidade; por isso 2 recebe um atalho de checagem antes de qualquer teste mais caro.
10^24 (um 1 seguido de 24 zeros), o limite onde o conjunto fixo de testemunhas do Miller-Rabin determinístico usado aqui (2 a 37) está matematicamente provado correto; acima disso, o mesmo conjunto deixa de garantir uma resposta certa.
Porque provar que um número é primo ou composto (Miller-Rabin) é muito mais barato do que encontrar os fatores exatos de um composto grande; a fatoração ainda usa divisão sucessiva, O(√n), então um composto com o maior fator primo perto de √n pode demorar visivelmente mais que a simples verificação de primalidade do mesmo número.
Suporta inteiros positivos até 10²⁴.
Os cálculos ficam apenas no navegador. Nenhum dado é enviado ao servidor.