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

O 2 e o único primo par, e a partir dele os primos vao rareando, mas nunca acabam (Euclides provou que são infinitos ha 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 contrario, fatorando o resultado.