Número primo

Os primos sao os blocos de construcao de todos os numeros: o teorema fundamental da aritmetica garante que qualquer natural maior que 1 se escreve como produto de primos de UM UNICO jeito (a menos da ordem). E o analogo matematico dos atomos: 60 = 2 x 2 x 3 x 5, e nao ha outra receita possivel. Por convencao, o 1 nao e primo, justamente para essa fatoracao unica funcionar.

Para testar se um numero e primo, basta tentar dividi-lo pelos primos ate a raiz quadrada dele: se nenhum divide, e primo. Para 97, a raiz fica entre 9 e 10, entao basta testar 2, 3, 5 e 7; como nenhum divide, 97 e primo. Para listar todos os primos ate um limite, o crivo de Eratostenes risca os multiplos de cada primo e e muito mais eficiente que testar um por um.

O 2 e o unico primo par, e a partir dele os primos vao rareando, mas nunca acabam (Euclides provou que sao infinitos ha mais de dois mil anos). Hoje eles sustentam a criptografia da internet: a seguranca de protocolos como o RSA depende de ser facil multiplicar dois primos gigantes e absurdamente dificil refazer o caminho contrario, fatorando o resultado.