Ir para o conteúdo
OneKitly

Provar que um milhão é primo custa mil divisões, não um milhão

Publicado a 16/11/2026 · 3 min de leitura · Calculadoras do dia a dia

Lena Hoffmann

Lena Hoffmann — Redatora de Ciência e Educação na OneKitly

Matemática · Física

Verificado a partir de 2 fontes

Ver perfil →
Em resumo

Para testar se um número tem um fator, nunca é preciso olhar para além da sua raiz quadrada. Se um número se parte em dois fatores, um está na raiz ou abaixo e o outro na raiz ou acima, pelo que não achar nada pequeno significa que não há nada de todo. Testar 1 000 003 pede portanto divisões de tentativa só até 1000, e sobrevive a todas: é primo. O seu vizinho 1 000 001 cai depressa, pois 101 divide-o exatamente e deixa 9901. A raiz quadrada é o que transforma uma busca impossível no trabalho de uma tarde, e é a primeira coisa que descobre quem escreve um teste de primalidade.

Publicidade

1 000 003 é primo e a prova para em 1000, a sua raiz quadrada. 1 000 001 não é, e a busca acaba à terceira tentativa: 101 divide-o.

Só os primos merecem ser tentados

Dividir por 4 é esforço perdido se 2 já falhou: a lista de candidatos não são os mil números abaixo da raiz mas os 168 primos que lá estão. Só isso divide o trabalho por seis, e saltar os pares e os múltiplos de três apanha quase de graça a maior parte do resto. A implementação clássica testa 2, depois 3, depois todo o número da forma «a um de cada lado de um múltiplo de seis», o que cobre todos os primos possíveis testando só um terço dos inteiros.

Porque o truque deixa de ajudar

Reduzir a metade o número de dígitos soa a muito até o número ser longo. A raiz quadrada de um número de 600 dígitos tem ainda 300, pelo que a divisão de tentativa sobre as chaves da criptografia moderna exigiria mais operações do que átomos há no universo observável. Os testes de primalidade reais abandonam portanto a divisão e usam testes probabilísticos cuja probabilidade de erro pode ser empurrada abaixo de qualquer limiar. Esses testes provam que um número é composto muito mais facilmente do que exibem um fator, que é justamente a assimetria em que assenta a segurança.

Trabalho necessário para testar um número por divisão de tentativa
NúmeroDivisões a tentarResultado
1 000 0013 antes de falhar101 × 9901
1 000 003168 primos até 1000Primo
Um número de 600 dígitosMais do que átomos no universoInutilizável
Verificador de número primoVerifica se um número é primo e encontra o seu menor divisor.Experimentar a ferramenta →
Publicidade

Perguntas frequentes

Porque 1 não é primo?
Por decisão, para manter única a fatorização. Se 1 contasse, 12 poderia escrever-se 2×2×3, ou 1×2×2×3, ou 1×1×2×2×3, e o enunciado de que todo o número tem exatamente uma fatorização prima precisaria de uma cláusula de exceção. As tabelas do século XIX listavam mesmo 1 como primo, e a convenção mudou porque cada teorema ficava mais limpo sem ele. As definições em matemática escolhem-se pelas suas consequências mais do que se descobrem, e este é o mais claro dos exemplos pequenos.
Como testo um número à mão?
Tome a raiz quadrada, arredonde para cima e divida por todos os primos até lá. Abaixo de dez mil isso são no máximo 25 divisões, a maioria das quais se descarta num instante: os pares falham com 2, as somas de dígitos divisíveis por três falham com 3, tudo o que acaba em 0 ou 5 falha com 5. O que sobrevive para ser testado a sério é uma lista curta. Acima do milhão o método torna-se fastidioso mais do que difícil, que é justamente o momento de o passar a uma máquina.

Artigos que podem interessar-lhe

Todos os guias →

Ferramentas relacionadas

Fontes

Detetaste um erro neste artigo?