Verificador de Número Primo

Veja se um número inteiro é primo, ou seja, divisível apenas por 1 e por ele mesmo e, se não for, os seus fatores primos quando dá para achá-los dentro do limite de cálculo. O verificador trata números abaixo de 3.317.044.064.679.887.385.961.981 com o teste determinístico de Miller–Rabin, então a resposta de sim ou não é exata, e não uma probabilidade. Ele também mostra os primos mais próximos, abaixo e acima do seu número.

Como usar esta ferramenta

1. Digite um número inteiro; vírgulas e espaços são ignorados.
2. Leia se ele é primo, composto ou nenhum dos dois (0 e 1).
3. Para um número composto, veja a fatoração em primos, o menor fator primo e a quantidade de divisores.
4. Use o primo anterior e o próximo para achar os primos mais próximos.

Fórmula

n é primo ⇔ n > 1 e nenhum primo p ≤ √n divide n

A divisão por tentativas até √n é o teste clássico dos livros. Para n grande, a calculadora usa o teste de Miller–Rabin com os 13 primos de 2 a 41 como bases, comprovadamente sem respostas erradas abaixo de 3,3 × 10²⁴. Os números compostos são então decompostos por divisão por tentativas e pelo método rho de Pollard. A quantidade de divisores vem da fatoração: se n = p₁^a × p₂^b × …, ele tem (a + 1)(b + 1)… divisores.

Exemplo

91: √91 ≈ 9,5, então só 2, 3, 5 e 7 precisam ser testados. 91 ÷ 7 = 13, logo 91 é composto: 91 = 7 × 13, com 4 divisores. 97: nenhum de 2, 3, 5 ou 7 o divide, então 97 é primo, e seus primos vizinhos são 89 e 101. 360 = 2³ × 3² × 5, que tem (3 + 1)(2 + 1)(1 + 1) = 24 divisores.