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!

44 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!

    1. Infelizmente isso parece ser contagioso… você escreve quase tão mal quanto elas! Não conhece infinitivo verbal e acabou de inventar uma nova palavra (siquer). Sem contar as demais asneiras…

  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