Verificador de números primos

Como usar o verificador de números primos

1. Escreve um Número inteiro. Também são aceites expressões: 2^61-1, 10^12+39, 20!+1 ou 3711.
2. A resposta aparece enquanto escreves; carrega em Verificar para dar mais tempo à decomposição de um número difícil.
3. Lê o veredicto, a Decomposição em fatores primos, o Número de divisores, o Primo anterior e o Primo seguinte. O painel Porquê explica como se chegou à resposta, e Copiar decomposição copia o produto de primos.
4. Para listar primos, preenche De e Até em Números primos num intervalo e carrega em Listar primos.

São aceites números até 2048 bits (cerca de 617 algarismos), e tudo é calculado no teu navegador.

O que torna um número primo

Um número primo é um número inteiro maior do que 1 cujos únicos divisores são 1 e ele próprio: 2, 3, 5, 7, 11, 13… Um número com outros divisores é composto e pode escrever-se de uma única forma como produto de primos, a sua decomposição em fatores primos (360 = 2³ × 3² × 5). Os números 0 e 1 não são primos nem compostos, e 2 é o único primo par.

O número de divisores resulta da decomposição: soma 1 a cada expoente e multiplica. 360 = 2³ × 3² × 5 tem (3 + 1)(2 + 1)(1 + 1) = 24 divisores. Um primo tem sempre exatamente 2.

Como funciona o teste

• Os números pequenos (inferiores a um milhão) são verificados por divisões sucessivas: se nenhum primo até à raiz quadrada divide o número, ele é primo. Não é preciso ir mais longe, porque um número composto tem sempre um fator que não ultrapassa a sua raiz quadrada.
• Os números maiores são primeiro divididos por todos os primos inferiores a 1000 e depois submetidos ao teste de Miller–Rabin. Com as 13 bases 2, 3, 5, …, 41, está provado que este teste é exato para todos os números inferiores a 3,3 × 10²⁴, o que inclui todos os inteiros de 64 bits. Para esses números, a resposta é certa.
• Acima de 3,3 × 10²⁴ são usadas 25 bases, e um número que passa todas é indicado como provável primo. A probabilidade de erro é inferior a 1 em 10¹⁵, mas não é uma prova matemática. Quando o teste falha, o número é certamente composto.

Como os números são decompostos

Os fatores pequenos são encontrados por divisões sucessivas. As partes compostas maiores são separadas com o algoritmo rho de Pollard (variante de Brent), que encontra fatores até cerca de 10 algarismos numa fração de segundo. Números mais difíceis, como o produto de dois primos com 15 ou mais algarismos, podem demorar muito mais do que qualquer limite de tempo, por isso a decomposição para ao fim de alguns segundos. O último fator fica então assinalado como composto mas não decomposto, e carregar de novo em Verificar dá-lhe mais tempo.

Primos num intervalo

A lista do intervalo usa um crivo de Eratóstenes segmentado, que risca os múltiplos de cada primo. Aceita até 1 000 000 de números por intervalo, com um limite superior até 10¹². A contagem abrange o intervalo inteiro, e são listados os primeiros 2000 primos. Por exemplo, há 25 primos entre 1 e 100 e 78 498 abaixo de um milhão.