Algoritmos Computacionais

Crivo de Eratóstenes

June 17, 2007

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  

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

/* Quarto passo */
para i  2 até raiz
    se vetor[i] = i
        imprima "O número " i " é primo."
        para j  i+i até valorLimite, de i e i
            vetor[j]  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!

Compare Preços de: notebooks, acer aspire, hp pavilion, computadores, pentium 4, nintendo wii, ps3, celulares, câmeras digitais

Categoria(s): Curiosidades

8 comentários

Escreva um comentário

Dados pessoais

Seu e-mail não será publicado, mas você deve informá-lo para o autor poder responder seu comentário.

• Nome
• E-mail
• Website

HTML 4.01 Strict: Você pode usar as seguintes tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Artigos relacionados:

Nenhum post relacionado.

53 assinantes

Mais artigos

• Crivo de Eratóstenes
• Escada perfeita (OBI2006)
• Grafos Ponderados
• Representando Grafos na Programação
• Os Grafos e o Orkut
• Conclusão sobre Ordenação
• Mini-Poker
• Ordenação por Seleção
• Ordenação por Inserção
• Introdução à Ordenação
• Recursão
• Análise de Algoritmos
• Qual a utilidade do algoritmo?
• Como representar um algoritmo?
• O que é um algoritmo?

Comentários recentes

• Matheus Eduardo Maura: Faço engenharia eletrica-eletronica( UNIRP SÃO JOSE DO RIO PRETO), e...
• rafael: muito legal o artigo mas teria como resolver esse algoritmo nao consegui de jeito nenhum,...
• Roger: Bom artigo. Podia atualizar esse site
• Aline Celestrino Bento: o que É ALGORITMO=exemplo:35 :7 porque eu ñ sei ALINE
• Claudio: eu gostaria de saber este algoritmo: faça um algoritmo que determine, para um digrafo,...
• ingrid morgana gomes paes: que bacana que legau isso e emtesamte e legau para apremder mais a...
• Filipe Névola: filipe.bico@hotmail. com
• Filipe Névola: Boa noite, gostaria de saber se você tem alguma implementação de menor caminho...
• Carlos Luiz Silva Meirelles: estou fazendo curso de informática gratuito patrocindo pelo estado....
• Maria Regina de Queiroz: Olá Tiago, li os seus artigos e gostei muito, gostaria se possivel que...

Categorias

• Algoritmos gulosos
• Básico
• Curiosidades
• Grafos
• Ordenação

Escrevo também...

• Tiago Madeira
  Site pessoal e blog do autor destes artigos
• Mal Vicioso
  Blog sobre filosofia e sobre a hipocrisia da sociedade

Links

• USACO Training Gateway
• Universidad de Valladolid
• Programming Challenges
• Olimpíada Brasileira de Informática
• International Olympiad in Informatics

Sobre o design

Este design foi copiado do CSS Zen Garden e modificado com autorização de seu autor, Gunta Klavina.

Licença

Todo o conteúdo deste site (incluindo textos, imagens, arquivos de áudio e quaisquer outros trabalhos), exceto quando especificado o contrário, está licenciado por Tiago Madeira sob uma Licença Creative Commons.