Números primos - Veja algoritmo para encontrá-los

Um número natural é primo se ele possui apenas dois divisores positivos e distintos. Ou seja, um número natural é primo se ele é maior que 1 e é divisível apenas por si próprio e por 1.

Um exemplo: o número 2. Ele só é divisível por ele mesmo, e por 1. O mesmo vale para 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37... Como se pôde observar, com exceção do 2, todos os demais números primos são ímpares. Observe também que essa definição exclui o 1 como primo.

O matemático grego Euclides provou que os números primos eram infinitos. Problemas envolvendo números primos mantiveram ocupados quase todos os matemáticos desde a antiguidade: como saber se um número é primo ou não, ou prever a sua existência em um conjunto de números, ou ainda encontrar uma fórmula para defini-los?

Muitas dessas questões continuam sem resposta, mas Eratóstenes criou um método para descobrir os primos em uma sequência de números naturais de 1 até n. Eratóstenes viveu em Alexandria algumas décadas depois de Euclides. Foi diretor da famosa Biblioteca de Alexandria e do Museu, enquanto acumulava uma série de outras atividades.

Algoritmo para definir números primos

O algoritmo se baseia numa "peneira": ele vai testando se um número é primo e, se for, elimina todos os seus múltiplos. Pode-se começar com um conjunto de números naturais não-nulos. Observe uma lista com os 50 primeiros:

O menor número primo é o 2, mas qualquer outro que seja divisível por 2 não é primo, certo? Então, mantém-se o 2 e excluem-se todos os seus múltiplos,

o que elimina metade da lista!

O próximo número primo é 3. Deve-se mantê-lo e excluir os múltiplos de 3, uma vez que um número múltiplo de 3 não pode ser primo:

E o 4? Quando se eliminam os múltiplos de 2, também se eliminaram os múltiplos de 4, 6, 8, e todos os números pares! É por esse motivo que o crivo é tão eficiente: ao excluir os múltiplos de um número primo, não há necessidade de verificar aqueles múltiplos.

Daí, pode-se passar ao próximo número da sequência, que é exatamente o próximo primo, o 5. Removendo os múltiplos de 5 (a essa altura, só restam o 25 e o 35) e fazendo o mesmo com o próximo da sequência que é o 7 (removendo apenas o 49), fica-se assim:

Todos os números que sobraram na lista são primos!

Múltiplos de 11

Você poderia se perguntar se o correto não seria continuar com a checagem até chegar ao fim da lista. Uma análise mostra que esse trabalho não é necessário. Veja que os próximos na verificação e exclusão da sequência seriam os múltiplos de 11, mas todos já foram excluídos previamente porque eram múltiplos de outro primo menor!

Observe o aspecto das últimas exclusões:

21 = 7x3 - 27 = 3²x3 - 25 = 5x5 - 35 = 7x5 - 49 = 7x7

Qualquer outro número não-primo nessa sequência deve ser da forma 11k, em que k é primo menor que 11, mas esses já foram excluídos! Então, os que sobraram são mesmo primos. Na verdade, basta calcular os números primos anteriores à raiz quadrada de n (você sabe dizer por quê?).

Divisão por tentativa

Para determinar se um certo número inteiro pequeno é primo, a divisão por tentativa funciona bem. Basta dividi-lo por todos os primos menores ou iguais à sua raiz quadrada. Se você estiver procurando por um primo gigantesco, com mais de 10.000 dígitos decimais, nunca poderia dividi-lo por todos os primos menores que a sua raiz quadrada.

Ainda assim, mesmo nesses casos a divisão por tentativa é utilizada, somente para fazer um rastreamento inicial. Fazem-se divisões por alguns milhões de primos pequenos e depois aplica-se um teste de primalidade. No caso de n ter 25 dígitos ou mais, a divisão por tentativa usando primos menores que sua raiz quadrada é impraticável. Se n tiver 200 dígitos, então a divisão por tentativa é impossível.

A mais importante utilização atual dos números primos é o reforço nos sistemas de segurança em criptografia, entre outras aplicações. Pode-se dizer que um sistema criptografado é tão mais seguro quanto maiores forem os primos utilizados na sua estrutura. A questão então passa por determinar se um número é primo ou não.

Mas por que o nome "primo"?

A palavra primo refere-se a ideia de primeiro, e sua origem está na concepção numérica da escola pitagórica, no século 5 a.C. Nessa época, os matemáticos gregos dividiam os números inteiros naturais em três classes: