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!

38 thoughts on “Crivo de Eratóstenes

  1. Muito bom, bom mesmo.Muito obrigado pelo ensinamento, pois irá me ajudar bastante.Paz e saúde para ti.

  2. parabens..
    muito bom seu site
    estou adorando…
    semear conhecimento é a melhor forma de de
    semear igualdade…
    parabens

  3. Acabei de ler :)
    Acho até que vou estudar e participar da Olimpíada nesse 2008!

  4. Bom…
    Primeiro gostaria de dizer que a questão matemática exposta aqui é citado no livro O Homem que Calculava de Júlio César de Melo e Sousa ( Malba Tahan )escritor, professor universitario e conhecedor da cultura Árabe. No Capítulo onde fala do “homem que não podia olhar para o céu”: Eratóstenes – filósofo grego. No livro é citado os cálculos do atrônomo, inclusive a descoberta da costelação de Sirius. Alfa do Cão Maior. nota do proprio autor.

  5. que bacana que legau isso e emtesamte e legau para apremder mais a matematica e buscar o que e eratotene vc que aimda nao conemseu o que e eratotenes connhesa e apramda mais matematica

  6. bem…..
    n perSebo mt diSto xD
    MELHOR DISEMDO N PERSEBO ND LOOL
    MAS APRESIO_TE TIAGO MADEIRA TENS PAXSENSIA PA FAZER ISTO
    LOOL XD BJS

  7. Olá, no comentário (4) o Gustavo afirma que há uma falha, já que o algoritmo faz o teste até a raiz quadrada de MAX.

    Na realidade não há problema algum com isso!

    Sou matemático e posso afirmar que para verificar se um número é primo, basta verificar se ele é ou não divisível por qualquer fator primo menor do que ou igual à sua raiz quadrada.

    Obviamente, se o número possuir raiz exata ele não é primo, portanto o problema é, como verificar até a raiz se ele pode não ser exata? Ora, basta tomar a parte inteira da raiz mais um.

    Ex: Se a raiz do número for 7,33, basta verificar se o número em questão não é divisível por nenhum primo até 7+1=8, ou seja, 2, 3, 5 e 7. Se ele não for divisível, podemos afirmar que o número é primo, caso contrário é um número composto.

    Valeu!

  8. Cara eu tenho 13 anos e estou começando a aprender isso
    mais é muito complicado!! :(

  9. é eu concordo com a leticia é muito complicado mesmo!! eu não entendi nadinha!! :(

  10. meu nome é janaina tenho 12 anos
    e adorei a esplicação apesar de ser
    muito dificil adorei
    miuto obrigada pela as esplicações
    beijos

  11. Algoritmo tranquilo. So que tem 2 problemas na implementacao em C:
    #1 – O vetor de tamanho “NMAX” (1000000) eh muito pra alocar na pilha, deve ser alocado via heap (malloc)
    #2 – O programa removeu os itens que nao sao primos, mas so imprime os primos ate a raiz do maximo. Um while() apos o for() fez o restante.

    Aqui esta o codigo alterado e compilando com gcc 4.4.0:

    #include
    #include
    #include

    int main(int ArgCount, char **ArgValue)
    {
    int i, j, *vetor;
    int valorMaximo, raiz;

    /* Veerifica se pasou o numero certo de parametros */
    if(ArgCount != 2)
    {
    printf("Erro na chamada: crivo.exe \nUm abraco, vai na sombra!\n");
    return(1);
    }

    // Primeiro passo
    printf("=== Crivo de Erathostenes ===\n");
    valorMaximo = atoi(ArgValue[1]);
    printf("Calculando numeros primos ate %d.\n", valorMaximo);

    // aloca memoria para o vetor
    vetor = (int*)malloc((valorMaximo + 1) * sizeof(int));

    // 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("Numero %3d eh primo!\n", i);

    // percorre todos os multiplos deste valor
    for(j = i + i; j <= valorMaximo; j += i)
    {
    // removendo da lista
    vetor[j] = 0;
    }
    }
    }

    /* meu quinto passo */
    while(i <= valorMaximo)
    {
    /* Se tem valor no vetor, imprime */
    if(vetor[i])
    {
    printf("Numero %3d eh primo!\n", i);
    }

    i++;
    }

    /* Libera a memoria usada */
    free(vetor);

    return(0);
    }

  12. Excelente material. Parabens pelo Site! Atualize sempre que possível.

  13. Tem umas retardada aqui que nem escreve nao sabem!
    Nezita e Ingrid sao as mesmas pessoas, ou sao duas que tem que voltar ao primario antes de siquer pensar em fazer programação!
    Ma va lava o cú com soda!

  14. To tentando entender isso tudo pra poder auxiliar meu filho que faz ads, mas tá muito dificil,,,qual seria o melhor livro para comprar.

  15. engraçado essa galera que faz ADS, nego sabe fazer script de mirc e macro no word e acha que vai ser programador. ai fica se perdendo em crivo de eratostenes, quero ver entender p vs. np

  16. haha…o cara ficou bravinho pk elas digitaram errado e fez isso tb…
    >>siquer<<

  17. Eu estou estudando fundamentos de programação e tenho uma versão em Pascal que não acha raiz e não entendi como se processa em Pascal. Você conhece ou quer te envie, para poder me explicar?
    Obrig., Marcelo

  18. Eu também estou a dar isso mas ainda não entendi algumas coisas!
    E por isso tenho muitas dúvidas! :( :)

  19. Cara amiga é simples fazer isso, mas o segredo não digo!
    Boa sorte para vocês todos e continuem com dúvidas para ficarem melhores alunos!
    Porque se tiverem dúvidas e disserem ao vosso professor ele diz para toda a turma e por isso ele diz: Boa, continua a fazer essas dúvidas e compreenderás melhor as tuas dúvidas!
    É de facto um caso interessante resolver isso mas continuem!
    :) (O) (P) (C)

  20. Tiago Madeira, seu link da USACO (com o interessante problema dos “números primos palíndromos”) está pedindo senha e login e isso certamente, quase nenhum dos usuários/visitantes deste seu blog de algoritmos aqui possui …

    De qualquer forma, como não desisto fácil da minha curiosidade, fuçando no google, consegui achar alguns problemas da mesma USACO sobre estes nr°s primos citados e os coloco aqui com os links de acesso [e sem pedir senha ... affffff], mas com um porém: os textos estão inglês.

    http://hi.baidu.com/hycdqzc/blog/item/ea7c666245976649eaf8f868.html

    http://greenmoon55.com/usaco-prime-palindromes/

    Enfim, espero ter ajudado a todos os curiosospelos nr°s primos … !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

    Adeus.

  21. Isto é muito confuso e eu tenho um enigma e quero saber a resposta.
    Cá vai: Constrói um crivo de eratostenes com todos os números de 1 a 50, mas coloca na primeira linha menos de 10 números. Indentifica as principais diferenças entre este crivo e o crivo inicial.

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>