Neste texto vamos aprender um método de encontrar todos os números primos de 1 até um certo limite: O Crivo de Eratóstenes. Esse método é bastante simples e pode ser reproduzido aí na sua casa. Também você vai encontrar um algoritmo em C para reproduzir o crivo.
O método leva o nome de Eratóstenes pois teria sido criado por ele. Eratóstenes foi um matemático grego que viveu no século no século III a.C. e foi o terceiro bibliotecário-chefe da Biblioteca de Alexandria.
Pequena revisão
Antes de ensinarmos como você pode montar seu próprio Crivo de Eratóstenes vamos fazer uma breve revisão sobre os números primos.
Um número natural é dito primo quando ele possui exatamente dois divisores, o 1 e ele mesmo.
Por exemplo, o número 2 é primo, pois só pode ser dividido por 1 e por 2. Por outro lado, o número 9 não é primo, pois além de ser divisível por 1 por 9 também é por 3.
O número 1 não é primo pois possui apenas um divisor.
O único primo par é o 2, pois todos os demais números pares são divisíveis por 2.
Os primeiros cinco números primos são: 2, 3, 5, 7 e 11. E, sabemos que existem infinitos números primos, e a demonstração para isso é bastante elementar, mas não é o objetivo deste texto.
O Crivo de Eratóstenes
O Crivo de Eratóstenes consiste em um algoritmo para encontrar primos, uma tarefa que pode ser bastante árdua até para um computador.
O diferencial desse algoritmo não é que ele é ótimo computacionalmente falando, mas que é demasiado simples de ser reproduzido até manualmente e permite a visualização de vários primos em ordem de uma vez.
Ele é bastante útil pela já citada (extrema) dificuldade que existe em encontrar números primos ou verificar se um número é primo, e com ele você pode rapidamente encontrar uma sequência de primos e usá-los para uma decomposição, por exemplo.
O Crivo vai funcionar da seguinte forma, escreveremos todos os números de 1 até o nosso limite e vamos riscando os que não são primos, ao fim do algoritmo os números que não foram riscados são primos.
A partir daqui segue as regras para montar o Crivo de Eratóstenes até 100. Você verá que é muito fácil mudar esse limite, deixando por conta do leitor montar com outros limites.
1. Escreva todos os números de 1 até 100.
2. Risque o número 1.
3. Siga em ordem fazendo o seguinte: se o número estiver riscado pule ele, se não estiver riscado marque ele como primo e risque todos os múltiplos dele.
4. Repita o passo 3 até o maior número natural menor ou igual a raiz de 100, no caso, até o 10.
Após seguir esses passos, todos os números não riscados são primos e nenhum primo terá sido riscado. Portanto você terá encontrado todos os números primos de 1 até 100.
Fácil, né? Você pode visualizar uma animação preenchendo o crivo até 120 clicando no seguinte link: Animação Crivo de Eratóstenes.
Programa em C com Crivo de Eratóstenes
Veja a seguir um programa na linguagem de programação C que utiliza o algoritmo que aprendemos para escrever todos os números primos até 1000.
void EscreverCrivo(){
int V[1001];
int i, j;
for(i=1;i<=31;i++) V[i]=1;
V[1]=0;
for(i=1;i<=1000;i++){
if(V[i]==0) continue;
for(j=2*i;j<=1000;j+=i) V[j]=0;
}
printf(“Numeros primos: \n”);
for(i=1;i<=1000;i++) if(V[i]==1) printf(“%d, ”, i);
}
Aprenda mais
Aqui no blog você poderá acompanhar vários outros textos que falam sobre números primos. Confira essa lista:
