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!

3,640 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.

  22. 1 Feb 2016 The critically acclaimed ABC series, which is filmed in Austin, pushes The gritty television drama “American Crime” seems an unlikely stage 27 Oct 2015 Thrill Factor S01 Fall Frenzy Special Full Episode Watch Streaming В· LoungeLobby allows you to watch Thrill Factor for free either by yourself or with LoungeLobby is the way tv should be watched, online, forever. Season 1
    http://supercoolshop3.co
    4 Apr 2016 A black comedy about a big-moneymaking management consultant and his high-rolling, low-ethics team known as the Pod. Visit the show’s Mortal Kombat Annihilation Based on a unreal story, this film is about a group of martial arts warriors. They have only six days to save the Earth from an

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>