Número primo

Os primos são os blocos de construção de todos os números: o teorema fundamental da aritmética garante que qualquer natural maior que 1 se escreve como produto de primos de UM ÚNICO jeito (a menos da ordem). É o análogo matemático dos átomos: 60 = 2 · 2 · 3 · 5, e não há outra receita possível. Por convenção, o 1 não é primo, justamente para essa fatoração única funcionar.

Para testar se um número é primo, basta tentar dividi-lo pelos primos até a raiz quadrada dele: se nenhum divide, é primo. Para 97, a raiz fica entre 9 e 10, então basta testar 2, 3, 5 e 7; como nenhum divide, 97 é primo. Para listar todos os primos até um limite, o crivo de Eratóstenes risca os múltiplos de cada primo e é muito mais eficiente que testar um por um.

O 2 é o único primo par, e a partir dele os primos vão rareando, mas nunca acabam (Euclides provou que são infinitos há mais de dois mil anos). Hoje eles sustentam a criptografia da internet: a segurança de protocolos como o RSA depende de ser fácil multiplicar dois primos gigantes e absurdamente difícil refazer o caminho contrário, fatorando o resultado.