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 — Redatora de Ciência e Educação na OneKitly
Matemática · Física
Verificado a partir de 2 fontes
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.
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.
| Número | Divisões a tentar | Resultado |
|---|---|---|
| 1 000 001 | 3 antes de falhar | 101 × 9901 |
| 1 000 003 | 168 primos até 1000 | Primo |
| Um número de 600 dígitos | Mais do que átomos no universo | Inutilizável |
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?