Crivo de Eratóstenes

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

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 \leftarrow \sqrt{valorLimite}

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

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

Vêem como é simples?

Crivo de Eratóstenes implementado em C

#include <stdio.h>
#include <math.h> // 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!

43 comentários sobre “Crivo de Eratóstenes

  1. 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.

  2. 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

  3. 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!

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

  5. 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);
    }

  6. 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!

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

  8. 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

  9. 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

  10. 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)

  11. 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.

  12. 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.

  13. Thiago, Estou fazendo a disciplina Algoritmos no meu mestrado mas nao tenho muita base, ja q sou Matematica. Meu professor ensinou o crivo e disse que a complexidade é n vezes raiz de n. Para mim era apenas raiz de n. Por que multiplica por n? Obrigada.

Deixe uma resposta