[Resolvido] Crivo de Erastótenes em C

vhbsouza · Julho 3, 2009

Olá pessoal!!!

Eu tenho que fazer um trabalho pra faculdade em que eu tenho que implementar o crivo de erastotenes em C usando listas encadeadas,

Mas eu não estou conseguindo fazer a remoção dos multiplos dentro do programa

Alguém pode me ajudar?

Crivo de Erastótenes - Wikipedia

int main()
{
   int i,j,num,raiz;
	lista *l=NULL;

   //Criação da lista até o numero limite
   scanf("%d",&num);
	for(i=2;i<=num;i++)
   	l=insere_fim(l,i);
	imprime(l);

   //Remocao dos multiplos
   raiz=sqrt(num);
   printf("\n\n\n\n\n\n");
}

quintelab · Julho 3, 2009

vhbsouza, o título do seu tópico vai contra a 9ª regra do fórum. Peça para o moderador da área editar ou faça caso consiga.

Regras do Fórum iMasters

Abraços...

VictorCacciari · Julho 4, 2009

vhbsouza

Vamos por partes aqui...

Cara, ninguém sabe o que é lista...

Assim fica difícil te ajudarmos..

ps.: se for postar o código e ele for grande, use um serviço de postagem, por favor. (www.codepad.org por exemplo)

O seu problema está onde??

Na manipulação da lista ou na implementação do crivo?

Abraços

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

ps.: Editei o título... Mas se seu problema estiver com a lista editarei novamente.

vhbsouza · Julho 5, 2009

vhbsouza

Vamos por partes aqui...

Cara, ninguém sabe o que é lista...

Assim fica difícil te ajudarmos..

ps.: se for postar o código e ele for grande, use um serviço de postagem, por favor. (www.codepad.org por exemplo)

O seu problema está onde??

Na manipulação da lista ou na implementação do crivo?

Abraços

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

ps.: Editei o título... Mas se seu problema estiver com a lista editarei novamente.

Então cara!!

Acredito que meu problema esteja na hora de usar o crivo porque minha lista fica quase perfeita.

A remoção de nós não funciona com os multiplos de 5 e 7 não sei pq:

Meu Codigo:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct no {
	int info;
   struct no *prox;
}lista;

lista *insere_fim (lista *l,int e);
lista *remocao_ord(lista *l, int e);
void imprime (lista *l);
int main()
{
   int i,j,num,raiz;
	lista *l=NULL,*aux;

   //Criação da lista até o numero limite
   scanf("%d",&num);

	for(i=2;i<=num;i++)
   	l=insere_fim(l,i);
	imprime(l);

   //Remocao dos multiplos
   raiz=sqrt(num);
   printf("\n\n\n\n");

   aux=l;

   for(i=2;i<=raiz;i++)
   {
		if((aux->info)%i == 0)
	  {
		 //printf("%d\t",aux->info);
			for(j=i*i;j<=num;j+=i)	   //nao consigo mexer daki pra frente
			{
				  aux=remocao_ord(aux,j);
		 }
	  }

	  //printf("%d\t",aux->info);
	  aux=aux->prox;
   }

	imprime(l);

   system("pause>0");
   return 1;
}


void imprime (lista* l)
{
   lista *p;   /* variável auxiliar para percorrer a lista, senão perderiamos o inicio da lista */
   for (p = l; p != NULL; p = p->prox)
	  printf("%d\t", p->info);
}

lista *remocao_ord(lista *l, int e)
{
	lista *p,*aux;
   /*Lista vazia ou elemento menor que o elemento menor da lista*/
   if((l!=NULL)&&(e>=l->info))
   {
   	//remove inicio
	  if(e==l->info)
	  {
		  p=l;
		 l=p->prox;
		 free(p);
	  }
	  else
	  {  // remove fim ou determinada posição
		  p=l;
		 while((p->prox!=NULL)&&(e>p->prox->info))
		 	p=p->prox;
		 if((p->prox!=NULL)&&(e==p->prox->info))
		 {
		 	aux=p->prox;
			p->prox=aux->prox;
			free(aux);
		 }
	  }
   }
   return(l);
}

lista *insere_fim (lista *l,int e)
{
	lista *novo, *p;

   novo=(lista*)malloc(sizeof(lista));
   novo->info =e;
   novo->prox=NULL;

   if (l==NULL)
   {
   	l=novo;
   }
   else
   {
   	p=l;
	  while(p->prox!=NULL)
		  p=p->prox;
	  p->prox=novo;
   }
   return l;
}

Socorro!!!

Estou a 4 Dias tentando fazer isso!!!

Suplicando por ajuda!!!

VictorCacciari · Julho 5, 2009

vhbsouza

Pois é...

teu problema é na implementação do crivo.

você ja tentou rodar isso ai com um debugger???

Se sim, deve ter notado que:

Na 3ª iteração do primeiro for (linha 33: for(i=2;i<=num;i++)) o valor de "i" é 4. Mas temos um problema... "i" não pode ser 4, pois ele ja foi removido do crivo (4 é multiplo de 2).

aux->info é igual à 5.

Ele não entra no if da linha 36, pois 5 % 4 != 0.

aux passará para o próximo item da lista, no caso 7 (pois 6 ja foi removido na primeira iteração).

o valor de i agora é 5, mas aux->info é igual à 7.

Não entrará no if da linha 36 novamente (que removeria os multiplos de "i", agora igual a 5)

Ja está tudo fora de sincronia... não vai mais remover nada. você só notou para 5 e 7, pois 6 = 3*2, 8 = 4*2 e 9 = 3*3, então os multiplos de 6, 8 e 9 ja são removidos ao remover os de 2 e 3.

Como resolver isso?

Muito simples.

Mude o for da linha 33 para: for(i=2;i<=num;i = aux->info)

Assim você pega o próximo número DA LISTA, não o "número + 1".

Outra coisa...

Era bom você criar uma funçãozinha pra liberar essa lista...

Espero que não tenha ficado muito confuso, qualquer coisa é só postar ai!

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

vhbsouza · Julho 5, 2009

vhbsouza

Pois é...

teu problema é na implementação do crivo.

você ja tentou rodar isso ai com um debugger???

Se sim, deve ter notado que:

Na 3ª iteração do primeiro for (linha 33: for(i=2;i<=num;i++)) o valor de "i" é 4. Mas temos um problema... "i" não pode ser 4, pois ele ja foi removido do crivo (4 é multiplo de 2).

aux->info é igual à 5.

Ele não entra no if da linha 36, pois 5 % 4 != 0.

aux passará para o próximo item da lista, no caso 7 (pois 6 ja foi removido na primeira iteração).

o valor de i agora é 5, mas aux->info é igual à 7.

Não entrará no if da linha 36 novamente (que removeria os multiplos de "i", agora igual a 5)

Ja está tudo fora de sincronia... não vai mais remover nada. você só notou para 5 e 7, pois 6 = 3*2, 8 = 4*2 e 9 = 3*3, então os multiplos de 6, 8 e 9 ja são removidos ao remover os de 2 e 3.

Como resolver isso?

Muito simples.

Mude o for da linha 33 para: for(i=2;i<=num;i = aux->info)

Assim você pega o próximo número DA LISTA, não o "número + 1".

Outra coisa...

Era bom você criar uma funçãozinha pra liberar essa lista...

Espero que não tenha ficado muito confuso, qualquer coisa é só postar ai!

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

Nossa cara, sua explicação me confundiu um pouco no começo mais eu consegui assimilar o Importante!!!

E consegui corrigir...

Por que, não tem como eu verificar um resto de divisão com um valor q não existe na lista!!!

Muito Obrigado!!!

Qnt à função que Libera a lista você pode me ajudar a faze-la?

ow me dar uma ideia de como ela funciona?

eu achei q dando free(l) bastaria

... dai percebi q dando free(l) ele so vai liberar o no inicial o restante ficará carregado não eh?

VictorCacciari · Julho 5, 2009

Nossa cara, sua explicação me confundiu um pouco no começo mais eu consegui assimilar o Importante!!!

hehehehe

Com um debugger você conseguiria "ver" aquilo que eu falei... talvez te clarease um pouco. Mas se o importante você pegou, ótimo!

Pra liberar a lista, é tranquilo, olha:

função: liberar_lista(lista *raiz)
	lista *aux = raiz
	enquanto aux não for nulo:
		tmp = aux
		aux = proximo_item(aux)
		liberar(tmp)

Não tem muito segredo! :P

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

vhbsouza · Julho 5, 2009

Nossa cara, sua explicação me confundiu um pouco no começo mais eu consegui assimilar o Importante!!!
hehehehe
Com um debugger você conseguiria "ver" aquilo que eu falei... talvez te clarease um pouco. Mas se o importante você pegou, ótimo!

Pra liberar a lista, é tranquilo, olha:
função: liberar_lista(lista *raiz)
	lista *aux = raiz
	enquanto aux não for nulo:
		tmp = aux
		aux = proximo_item(aux)
		liberar(tmp)
Não tem muito segredo! :P

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

Valeu Chará!!! uashduashda

Consegui fazer sim!!

Funcionou!! direitinho...

ow deixa eu te pergunta uma coisa:

eu to qrendo fazer uma função que concatena duas listas em uma ...

dai eu qria usar um for pra variar o end de uhttp://forum.imasters.com.br/style_images/10/folder_editor_images/rte-code-button.pngm ponteiro dessa forma:

for (p = l; p != NULL; p = p->prox)

pq senão eu teria que fazer assim neh:

p=l
while(p->prox != NULL)
	 p=p->prox;

O problema não é em escrever mais linhas de codigo .. eu so queria saber se funcionaria c eu usasse esse For ou invés do While!!!

você sabe?

t+ vlw

VictorCacciari · Julho 6, 2009

Cara, funciona sim!!

A sintaxe de um loop for é a seguinte:

for (condição_inicial; condição_de_saída; incremento)

e pode ser fácilmente traduzido para um loop while:

condição_inicial;
while (condição_de_saída)
{
//instruções

incremento;
}

Pode usar o for tranquilamente...

Eu sei que existem diferenças no código assembly de um for para um while. Até sei que para um loop infinito, mais vale usar for (;;) do que while(1).

Mas não sei quando compensa mais usar um ou o outro... vou estudar sobre e volto a postar!

=D

Abraços

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

Arquivado

[Resolvido] Crivo de Erastótenes em C

Recommended Posts

vhbsouza 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

quintelab 91

Compartilhar este post

Link para o post

Compartilhar em outros sites

VictorCacciari 42

Compartilhar este post

Link para o post

Compartilhar em outros sites

vhbsouza 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

VictorCacciari 42

Compartilhar este post

Link para o post

Compartilhar em outros sites

vhbsouza 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

VictorCacciari 42

Compartilhar este post

Link para o post

Compartilhar em outros sites

vhbsouza 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

VictorCacciari 42

Compartilhar este post

Link para o post

Compartilhar em outros sites

Fixar div até atingir uma certa altura

Ajuda com Extends e envio para o banco

PHP+Codeginiter - Orientação para Impressão

Fóruns

Tempo Real

Informação importante