Crivo de Eratóstenes

Encontrar números primos é um problema comum em olimpíadas e maratonas de programação. Até hoje não existe uma maneira fácil de determinar se um número é ou não primo, mas para resolver estes problemas é indispensável o conhecimento de alguns algoritmos clássicos e simples, como o Crivo de Eratóstenes.

O Crivo de Eratóstenes é um método bastante prático para encontrar os primos de 2 até um valor limite, que pode ser feito a mão e é fácil de implementar.

O algoritmo consiste em:

  1. Determinar (ou receber na entrada do programa) o valor limite, isto é, o maior número que desejamos saber se é primo.
  2. Fazer a raiz quadrada do valor limite. Pode-se arredondar para baixo caso a raiz não seja exata (e quase nunca é).
  3. Criar um vetor (lista) com os números de 2 até o valor limite.
  4. Para i=2 até raiz do valor limite, caso o número (i) não esteja riscado insira-o na lista dos primos (ou imprima-o, ou não faça nada, isso depende da utilidade que você quer dar para o crivo) e risque todos os seus múltiplos na lista.

Há várias maneiras de implementar este algoritmo. Eu pseudocodaria (meu pseudocódigo é bem próximo de uma linguagem normal, porque acho que assim é mais fácil de entender e depois implementar) ele assim:

/* Primeiro passo */
recebe valorLimite

/* Segundo passo */
raiz [tex]\leftarrow[/tex] [tex]\sqrt{valorLimite}[/tex]

/* Terceiro passo */
para i [tex]\leftarrow[/tex] 2 até valorLimite
    vetor[i] [tex]\leftarrow[/tex] i
fim-para

/* Quarto passo */
para i [tex]\leftarrow[/tex] 2 até raiz
    se vetor[i] = i
        imprima "O número " i " é primo."
        para j [tex]\leftarrow[/tex] i+i até valorLimite, de i e i
            vetor[j] [tex]\leftarrow[/tex] 0
        fim-para
    fim-se
fim-para

Vêem como é simples?

Crivo de Eratóstenes implementado em C

#include
#include
// necessário para raiz

#define NMAX 1000000 // valor máximo para o valor máximo

int main() {
int i, j, vetor[NMAX];
int valorMaximo, raiz;

// Primeiro passo
scanf("%d", &valorMaximo);

// Segundo passo
raiz=sqrt(valorMaximo);

// Terceiro passo
for (i=2; i<=valorMaximo; i++) {
vetor[i]=i;
}

// Quarto passo
for (i=2; i<=raiz; i++) {
if (vetor[i]==i) {
printf("%d é primo!\n", i);
for (j=i+i; j<=valorMaximo; j+=i) {
vetor[j]=0; // removendo da lista
}
}
}

return 0;
}

No USACO Training Program Gateway (programa de treinamento para olimpíadas dos estado-unidenses) há um problema muito interessante (Prime Palindromes) cujo objetivo é determinar palíndromos primos de X a Y. Uma das melhores situações que já encontrei para usar o Crivo e sem dúvidas é um ótimo treinamento. Além de determinar primos, você terá que determinar palíndromos e é outro ótimo exercício lógico-matemático.

Divirtam-se e qualquer dúvida usem os comentários!

9,253 thoughts on “Crivo de Eratóstenes

  1. That s the a requirement of interval training workouts. They simply sided with whatever parties that could advance their interests, he said. If you like to present your little ones some excitement, you will need not crash your price range as there is good deal in the achieve of your pocket amid the used laptop or computer games.”When you score two goals and give an assist for the third goal, then you are happy as a manager, but he is also very happy, I assume.Kidney:Kidney is the organ responsible for filtering blood from extra water, salt and other waste products in the human body.
    Jakub Zboril Jersey UK [url=http://www.uknhlshop.com/Cheap-Boston-Bruins-Jakub-Zboril-Jersey-Uk/]Jakub Zboril Jersey UK[/url]

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>