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!

Categoria(s): Curiosidades

28 comentários

#1 | Junio (17/06/2007)

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

#2 | mariano (23/08/2007)

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

#3 | andre (16/10/2007)

eu sou o andre e vai po caralho

#4 | Gustavo Felisberto (17/12/2007)

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

#5 | Felipe Schneider (26/12/2007)

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

#6 | Fabiano Lages Arouche (17/01/2008)

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.

#7 | ingrid morgana gomes paes (17/06/2008)

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

#8 | Roger (20/06/2008)

Bom artigo. Podia atualizar esse site

#9 | NEZITA (08/11/2008)

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

#10 | NEZITA (08/11/2008)

TENS PACIENCIA PA ISSO
JA EU…
LOOL XD BJS

#11 | Thalita (12/11/2008)

Perfeitooo!! Muito Obrigada!

#12 | José Sérgio (07/12/2008)

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!

#13 | Leticia (21/05/2009)

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

#14 | samela (21/05/2009)

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

#15 | janaina aparecida de souza (11/06/2009)

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

#16 | Mateus (16/06/2009)

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

#17 | Mateus (16/06/2009)

E para rodar:
crivo.exe

#18 | Mateus (16/06/2009)

maldito html …

pra rodar:

crivo.exe “valor maximo”

#19 | Juliano (19/06/2009)

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

#20 | yasmim (01/07/2009)

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

#21 | cocozito (06/12/2009)

que porcaria de site meu…

#22 | Dionis (19/01/2010)

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!

#23 | Joquim Floriano de Souza (25/04/2010)

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

#24 | Tiago Madeira (25/04/2010)

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

#25 | gui (25/04/2010)

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

#26 | cú preto (01/06/2010)

não gostei nada da resposta

#27 | cú preto (01/06/2010)

vcs não sabi esplicar

#28 | kah (26/08/2010)

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

Escreva um comentário

Para ler o que escrevo atualmente, visite meu novo blog.

Índice

Online Judges

Programming Contests

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 que permite que você copie, distribua, exiba, execute a obra e crie obras derivadas desde que mantenha os créditos, não use sua modificação para fins comerciais e compartilhe seu trabalho derivado pela mesma licença.

HTML 4.01 gerado por WordPress em 0.356 segundos.