Verificador de números primos

Este verificador de números primos diz na hora se um número inteiro é primo. Se não for, você vê a fatoração em primos e os divisores. Ele também mostra o primo anterior e o próximo, assinala primos gêmeos e primos de Mersenne, e explica cada passo para números até um trilhão. Na aba Primos num intervalo, você lista todos os primos entre dois números.

O que faz um número ser primo

Um número primo é um número inteiro maior que 1 com exatamente dois divisores: 1 e ele mesmo. 2, 3, 5, 7, 11 e 13 são os primeiros primos. 2 é o único primo par, porque qualquer outro número par é divisível por 2. Um número inteiro maior que 1 que não é primo se chama composto. 0 e 1 não são primos nem compostos.

Os primos são as peças que formam todos os números inteiros. O teorema fundamental da aritmética diz que todo número inteiro maior que 1 pode ser escrito de uma única forma como produto de primos, sem contar a ordem. Por exemplo, 360 = 2³ × 3² × 5. É essa fatoração que o verificador mostra para os números compostos.

Como o verificador funciona

Números pequenos e médios (até um trilhão): divisão por tentativa. Para testar n, o verificador divide n por cada primo até √n. Isso basta, porque se n = a × b, então a ou b tem de ser √n ou menor. Se nenhum desses primos divide n, n é primo. Para 1 000 000 007, √n ≈ 31 623, então ele testa os 3401 primos até 31 622 e vê que nenhum divide o número.

Números grandes: o teste de Miller-Rabin. Acima de um trilhão, o verificador usa o teste de Miller-Rabin. Todo primo ímpar p passa numa verificação que consiste em escrever p − 1 = 2ˢ × d e elevar um valor de teste (uma base) à potência d módulo p. Um número composto falha para a maioria das bases. Com os 13 primeiros primos (de 2 a 41) como bases, o teste está provado para todo número abaixo de cerca de 3,3 × 10²⁴. Para números maiores, usa 20 bases e indica o resultado como primo provável.

Fatoração: o método rho de Pollard. Para decompor um número composto grande, o verificador primeiro retira os fatores primos pequenos e depois usa o método rho de Pollard, que encontra um fator muito mais rápido que a divisão por tentativa. Números cujos fatores primos são todos muito grandes podem levar anos para ser fatorados em qualquer computador. Nesse caso, o verificador mostra a parte que não conseguiu decompor.

Primos num intervalo: o crivo. A aba de intervalo usa um crivo de Eratóstenes segmentado. Ele risca os múltiplos de cada primo até √(Até), e cada número que sobra é primo. Assim processa até um milhão de números de cada vez, em qualquer ponto até um trilhão.

Exemplos

• 221: √221 ≈ 14,9, então o verificador testa 2, 3, 5, 7, 11 e 13. 221 ÷ 13 = 17, logo 221 = 13 × 17 é composto. Muita gente acha que 221 é primo porque é ímpar e não termina em 5.
• 561: 561 = 3 × 11 × 17. É o menor número de Carmichael, um número composto que engana o teste simples de Fermat para qualquer base sem fatores em comum com ele. O teste de Miller-Rabin não tem essa fraqueza.
• 2 147 483 647: é 2³¹ − 1, um primo de Mersenne e o maior valor de um inteiro com sinal de 32 bits em programação. O verificador confirma que é primo e o assinala como primo de Mersenne.
• 600 851 475 143: = 71 × 839 × 1471 × 6857. O seu maior fator primo, 6857, é a resposta de um problema de programação conhecido (Project Euler, problema 3).

Os primos ficam mais raros à medida que os números crescem, mas nunca acabam. O teorema dos números primos diz que, perto de um número n, cerca de 1 em cada ln(n) números é primo. Perto de um trilhão, ln(10¹²) ≈ 27,6, então um bloco de 200 000 números deve ter cerca de 7238 primos. Entre 999 999 800 000 e 1 000 000 000 000 há 7213, o que você pode conferir com a aba de intervalo.

Onde os números primos são usados

• Segurança na internet: a criptografia RSA multiplica dois primos secretos com centenas de dígitos cada. Qualquer pessoa pode ver o produto, mas nenhum método conhecido consegue fatorá-lo num tempo razoável, e isso protege a chave.
• Programação: as tabelas hash costumam usar um número primo de posições para distribuir bem os dados, e problemas de competições pedem muitas vezes respostas módulo o primo 1 000 000 007.
• Recordes matemáticos: o projeto GIMPS procura primos de Mersenne muito grandes. Em outubro de 2024, encontrou 2^136 279 841 − 1, um primo com mais de 41 milhões de dígitos.
• Ensino: encontrar primos, fazer árvores de fatores e contar divisores são temas básicos na escola, e os passos detalhados mostram cada divisão.