Algoritmos Computacionais

Artigos sobre lógica de programação por Tiago Madeira

algoritmo: do Lat. algorithmos < Ár. alkharizmi: [Inform.] conjunto de etapas bem definidas necessárias para chegar à resolução de um problema.

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:

Determinar (ou receber na entrada do programa) o valor limite, isto é, o maior número que desejamos saber se é primo.
Fazer a raiz quadrada do valor limite. Pode-se arredondar para baixo caso a raiz não seja exata (e quase nunca é).
Criar um vetor (lista) com os números de 2 até o valor limite.
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 | 6 comentários

49 assinantes

Mais artigos

Comentários recentes

Luciano: Tiago eu tenho uma prova daqui a uma semana e não tenho ideia por onde começar a...
Irã Pezos: Sou estudante de Engenharia e gostaria de esta atualizado quando ao problemas e...
felippe santana: estou com dificuldade de desenvolver algoritmos em linguagem pascal de método...
karine: gostaria de saber cm se faz um teste de mesa …desde ja agradeço..
Caroline Rodrigues: Nossa! sou iniciante de um curso técnico de informática.. Parabéns aí,...
romeu queiroz: E.1.A.Q Dado um valor ele informa seu dobro.tiplos e quaduplos simultaneamente. se...
romeu queiroz: E.1.A.Q Mostre todos os multiplos de 5 existentes entre 1 e 1000
romeu queiroz: por favor me ajude E.1.A.Q Simule as compras em surmercado sabe-se que todos os...
EVELIN CAROLINE: OI EU QUERIA SABER COMO DESENVOLVER UM ALGORITMO QUE LEIA UMA TEMPERATURA EM...
EVELIN CAROLINE: EU ADOREI O CONCEITO SOBRE ALGORITMO

Categorias

Escrevo também...

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

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.

HTML 4.01 gerado por WordPress em 3.286 segundos.