Crivo de Eratóstenes

Os números primos possuem várias aplicações, como criptografia e segurança dos dados (por exemplo: SSL, X509, certificados, chaves privadas, ..), e a obtenção deles de forma eficiente sempre foi alvo de estudo dos matemáticos.

O Crivo de Eratóstenes é um algoritmo muito simples e eficiente para gerar números primos. Esse algoritmo consiste em remover os múltiplos de um determinando conjunto.
Por exemplo, quero achar todos os números primos de 1 a 120. O algoritmo gera um conjunto com todos os números de 2 a 120 (já que 1 não é primo). Utiliza o primeiro número (que no caso é 2), e vai removendo os múltiplos: 4, 6, 8, 10, .... e marca o 2 como primo, procura o próximo não removido que é o 3, marca como primo, e vai removendo os múltiplos se não foram removidos anteriormente: 6, 9, 12, 15... Ele vai fazendo isso até raiz quadrada do número máximo que você quer verificar. Se a raiz não é inteira, truncamos (menor inteiro). No nosso exemplo, raiz quadrado de 120, que fica entre 10 e 11 e portanto só precisamos verificar os múltiplos até 10. Garantindo que buscamos por todos os múltiplos possíveis até 120.

Share on Facebook

Tweet

Follow us