Tiago Madeira

Curiosidades

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

Comentários

Junio

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

mariano

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

andre

eu sou o andre e vai po caralho

Gustavo Felisberto

Isto está mal. Como se pode facilmente verificar ao correr este algoritmo ele apenas testa até sqrt(MAX), se MAX for primo, não vai ser testado e não será indicado. QED. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Felipe Schneider

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

Fabiano Lages Arouche

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.

ingrid morgana gomes paes

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

Roger

Bom artigo. Podia atualizar esse site

NEZITA

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

NEZITA

TENS PACIENCIA PA ISSO JA EU… LOOL XD BJS

Thalita

Perfeitooo!! Muito Obrigada!

José Sérgio

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!

Leticia

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

samela

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

janaina aparecida de souza

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

Mateus

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);

}

```

Mateus

E para rodar: crivo.exe =]

Mateus

maldito html … pra rodar: crivo.exe “valor maximo”

Juliano

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

yasmim

Nossa…estou no 5° ano e estou aprendendo isso!!facil

cocozito

que porcaria de site meu…

Dionis

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!

Sincero

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…

Joquim Floriano de Souza

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

Tiago Madeira

Senhor, se quer mesmo auxiliar seu filho deixe-o em paz.

gui

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

cú preto

não gostei nada da resposta

cú preto

vcs não sabi esplicar

kah

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

ilis

eu estou estudando isso i achei ñ muito complicado!

Marcelo

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

vixi

assim nao pode…

Jakapa

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

Jcccp

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) ©

len

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.

eu

ñ tendi nada!!! kkk

pamela

o seu site e muito mal cara fais outro pela mor em.

pamela

muito mallllllllllllllll

Jose Paulo

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.

Carolina

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.

Tiago Madeira

Oi Carol, você está certa. A complexidade é raiz de N, não N raiz de N.

vitoria

agora estou comecado a entender tem que tira todos os multiplos dos numeros na prova acho que vou acerta vou tira um 100

vitoria

vitopria disse apredi vou tira um dez na prova eu acho bjs

Crivo de Eratóstenes (números primos). | luisthiago

[…] Imagem retirada do http://tiagomadeira.com/2007/06/crivo-de-eratostenes/ […]

yohanna felix

Teria como passar para a linguagem javascript sem muita mudança ?

Obrigado! Seu comentário foi enviado e será publicado quando for aprovado.

Infelizmente ocorreu um erro ao enviar seu comentário.