Um verificador de números primos que mostra a prova
Digite qualquer número inteiro neste verificador de números primos e descubra na hora se ele é primo ou composto. Se for composto, você recebe a fatoração completa em primos (com expoentes, como 48 = 2⁴ × 3), uma árvore de fatores desenhada e uma escada de divisões; nos dois casos você vê o primo anterior e o seguinte e a quantidade de divisores. Um segundo modo lista e conta todos os primos de um intervalo, dos 25 primos abaixo de 100 aos 78,498 abaixo de um milhão.
O verificador usa os mesmos métodos dos programas de teoria dos números: divisão de teste e crivo de Eratóstenes para números pequenos, um teste de Miller–Rabin determinístico para números de até 3.3 × 10²⁴ e o algoritmo rho de Pollard para quebrar compostos grandes. Funciona com números de até 300 dígitos, tudo dentro do seu navegador.
Como usar o verificador de números primos
- Escolha Verificar um número ou Primos em um intervalo.
- Para verificar um número, digite-o: vírgulas e espaços são ignorados, então 1,000,003 funciona.
- Leia o veredito e depois os quadros: fatoração em primos, menor fator primo, quantidade de divisores, primo anterior e primo seguinte.
- Para um intervalo, informe onde começar e onde parar. Abaixo aparecem a quantidade, o menor e o maior primo, os pares de primos gêmeos e a lista completa.
- Para um número composto, estude a árvore de fatores (os círculos preenchidos são os primos) e a escada ao lado.
- Abra “Como sabemos” para ver por que a resposta está certa e use “Copiar lista” para levar os primos para outro lugar.
Recursos do verificador de números primos
Comprovado, não chutado
Abaixo de 3.3 × 10²⁴ as bases de Miller–Rabin usadas são comprovadamente capazes de pegar todo composto, então “primo” quer dizer primo.
Fatoração completa
Números compostos são quebrados em potências de primos como 2³ × 3² × 7, incluindo números de 20 dígitos pelo método rho de Pollard.
Árvore de fatores e escada
Os dois métodos ensinados na escola são desenhados para você: a árvore separa o menor primo a cada passo e a escada divide por primos até chegar a 1.
Primos mais próximos
O primo anterior e o seguinte são encontrados para números de qualquer tamanho, útil em hash, exercícios de criptografia e quebra-cabeças.
Listas de primos rápidas
Um crivo segmentado conta primos em intervalos de até 10 milhões de números em uma fração de segundo.
Resultados explicados
Regras de divisibilidade, o limite da raiz quadrada na divisão de teste e o teorema dos números primos aparecem junto com a resposta.
O que é um número primo?
Um número primo é um inteiro maior que 1 cujos únicos divisores são 1 e ele mesmo: 2, 3, 5, 7, 11, 13 e assim por diante. Um inteiro maior que 1 que não é primo é composto: pode ser escrito como produto de números menores, como 221 = 13 × 17. O número 1 não é nem um nem outro, e o 2 é o único primo par.
Todo inteiro acima de 1 pode ser escrito como produto de primos de uma única maneira (o teorema fundamental da aritmética). Por isso os primos são chamados de blocos de construção dos números, e por isso as fatorações servem para achar o MMC e o MDC e simplificar frações.
Como verificar à mão se um número é primo
- Use primeiro as regras rápidas. Números pares (exceto o 2) são compostos; se a soma dos algarismos é divisível por 3, o número também é; números que terminam em 0 ou 5 são divisíveis por 5.
- Teste só até a raiz quadrada. Se n = a × b, um entre a e b é no máximo √n. Para conferir 221 você só precisa dos primos até 14: 2, 3, 5, 7, 11 e 13, e o 13 o divide.
- Teste só primos. Divisores compostos não acrescentam nada.
- Cuidado com os enganadores. 51 (3 × 17), 57 (3 × 19), 91 (7 × 13) e 221 (13 × 17) costumam ser confundidos com primos.
Quantos números primos existem?
Euclides provou há mais de 2,000 anos que os primos nunca acabam. Eles ficam mais raros: cerca de 1 em cada 4 números abaixo de 100 é primo, mas só cerca de 1 em 13 abaixo de um milhão. O teorema dos números primos diz que a quantidade de primos até x é aproximadamente x ÷ ln x, e o modo de intervalo compara essa estimativa com a contagem real.
| Até | Quantidade de primos | Maior primo do intervalo |
|---|---|---|
| 10 | 4 | 7 |
| 100 | 25 | 97 |
| 1,000 | 168 | 997 |
| 10,000 | 1,229 | 9,973 |
| 100,000 | 9,592 | 99,991 |
| 1,000,000 | 78,498 | 999,983 |
Verificador de números primos: perguntas frequentes
Como sei se um número é primo?
Veja se algum primo até a sua raiz quadrada o divide. Se nenhum dividir, ele é primo. O verificador faz isso (ou um teste de Miller–Rabin para números grandes) e mostra o resultado com o raciocínio.
O 1 é um número primo?
Não. Um primo precisa ter exatamente dois divisores diferentes, e o 1 tem só um. Tratar o 1 como primo também quebraria a regra de que todo número tem uma única fatoração em primos.
Quais são os números primos de 1 a 100?
São 25: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 e 97. Escolha “Primos em um intervalo” e digite de 1 a 100 para listar e copiar.
Que tamanho de número este verificador aguenta?
Até 300 dígitos. Números abaixo de 3.3 × 10²⁴ recebem uma resposta comprovada; os maiores recebem uma resposta probabilística de Miller–Rabin, com chance de erro muito menor que a de uma falha de hardware. Fatorar compostos muito grandes pode ser lento, então um fator grande que não se quebra rápido aparece entre parênteses.
Por que os números primos são importantes?
Eles sustentam a teoria dos números e a criptografia moderna: a criptografia RSA depende de que multiplicar dois primos grandes é fácil, mas desfazer o produto é extremamente difícil. Os primos também aparecem em hash, geração de números aleatórios e códigos corretores de erros.
Como acho a fatoração em primos de 48?
Divida pelo menor primo que couber até chegar a 1: 48 ÷ 2 = 24, ÷ 2 = 12, ÷ 2 = 6, ÷ 2 = 3, ÷ 3 = 1. Isso dá 48 = 2 × 2 × 2 × 2 × 3 = 2⁴ × 3. Uma árvore que começa com 6 × 8 chega aos mesmos primos. Digite 48 acima para ver as duas figuras.
O que é um número de Carmichael?
Um número composto, como 561 = 3 × 11 × 17, que passa no teste de primalidade de Fermat para toda base coprima com ele. O verificador os sinaliza e usa o teste de Miller–Rabin, mais forte, que os números de Carmichael não enganam. Você também pode explorar fatoriais de primos na calculadora de fatorial.