Crivo de Eratóstenes com recursividade

giggs
(usa FreeBSD)

Enviado em 01/09/2012 - 17:06h

Oi gente

tenho um exerciciu da faculdade onde tenho que criar um algoritmo em C do Crivo de Eratóstenes (http://pt.wikipedia.org/wiki/Crivo_de_Erat%C3%B3stenes).

Eu fiz o algoritmo normal, com e sem função, mais o professor quer com Recursividade e eu nao acho maneira alguma de fazer com recursividade.

Alguem poderia me ajuda?

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#include <conio.h>



int func_crivo(int n, int vetor[])   

{    

     int i,j;

     

    /* Inicializa o crivo                      */

      for (i = 2; i <= n; i++)

         vetor[i] = 1;

      

      i = 2;

      while (i * i <= n)

      {

        /* Marca os multiplos de i.                */

        for (j=i+1; j<=n; j++)

          if (vetor[j]!=0 && j % i ==0)

            vetor[j] = 0;

    

        /* Pula nao primos ate proximo primo.      */

        for (j = i + 1; vetor[j] == 0 && j <= n; j++);

        i = j;

      }      

}





main ()

{

          int vetor[1000],i,j,n;

    

      printf("Digite o limite superior: ");

      scanf("%d", &n);

    

      func_crivo(n,vetor);

      

      /* Impressao dos primos. */

      for (i = 2; i <= n; i++)

        if (vetor[i] != 0)

          printf ("%d ", i);

      

      getch();

}

 

Aguardo resposta, obrigado.

lcavalheiro
(usa Slackware)

Enviado em 01/09/2012 - 17:31h

Eu não entendo de programação mas recursividade é algo que eu sei um pouquinho. Dentro do algoritmo você faz o seguinte:

1) estabelece uma variável que vai determinar o valor máximo do cálculo;
2) estabelece outra variável que vai ser o valor inicial (no caso do crivo, 2)
3) crie uma única função que:
a) verifica se a segunda variável é menor que a primeira. Se for maior, a função encerra o programa;
b) se for menor, a função faz o algoritmo do cálculo e armazena todos os números gerados em uma matriz de dados
c) chama o menor valor que não esteja na matriz de dados e faz com que a segunda variável seja igual a esse número
d) chama a função de novo.

giggs
(usa FreeBSD)

Enviado em 01/09/2012 - 18:02h

Infelizmente ainda nao consigo imaginar a lógica pra esse problema. Mas obg.

lcavalheiro
(usa Slackware)

Enviado em 01/09/2012 - 18:14h

Eu não sou programador, mas o raciocínio é mais ou menos o seguinte, em linguagem mais ou menos natural:

valor_maximo = x
valor_inicial = 2
:inicio_do_loop
se valor_inicial => valor_maximo, então exit
for multiplos de valor_inicial até x step valor_inicial; do ponha multiplos em matriz_de_dados; done
valor_inicial = menor ( matriz_de_dados )
voltar inicio_do_loop

Agora tem uns detalhes:

1) Eu não sei como criar uma variável em matriz em C (na verdade eu não sei nem se o nome é esse, mas você pode ter uma idéia do que estou falando);
2) Eu não sei como puxar a menor variável de uma matriz, então não me pergunta como fazer isso?

lcavalheiro
(usa Slackware)

Enviado em 01/09/2012 - 18:32h

Definição recursiva: é uma regra de definição que usa a própria regra pra gerar a regra. Exemplo de definção recursiva pra operação de sucessor natural de um número usando a adição:

1) sucessor ( 0 ) = 1
2) sucessor ( a ) + 1 = sucessor ( a + 1 )

Exemplo:

5 = sucessor ( 4 ) = sucessor ( 3 + 1) = sucessor ( 3 ) + 1 = sucessor ( 2 + 1 ) + 1 = sucessor ( 2 ) + 1 + 1 = sucessor ( 1 + 1 ) + 1 + 1 = sucessor ( 1 ) + 1 + 1 + 1 = sucessor ( 0 + 1 ) + 1 + 1 + 1 = sucessor ( 0 ) + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1

Outro exemplo:

sucessor ( 0 ) = 1
sucessor ( 1 ) = sucessor ( 0 + 1 ) = sucessor ( 0 ) + 1 = 1 + 1 = 2
sucessor ( 2 ) = sucessor ( 1 + 1 ) = sucessor ( 1 ) + 1 = sucessor ( 0 + 1 ) + 1 = sucessor ( 0 ) + 1 + 1 = 1 + 1 + 1 = 3

Função recursiva, como você pode ver aí em cima, é uma função que tem uma definição recursiva em sua chamada.

dms_
(usa elementary OS)

Enviado em 01/09/2012 - 18:47h

Seguinte, criptografia RSA é baseada em numeros primos, então descobrir se um numero e primo ou não de 1000 para baixo é ralativamente "facil" agora mais que isso, se torna uma tarefa grandiosa, em vista que a empresa RSA paga para quem descobrir o maio numero primo possivel...
Enfim,

Você vai ter que mecher com vetores.
http://www.algorithmist.com/index.php/Prime_Sieve_of_Eratosthenes.c

Espero que não copie e cole o item acima, mas sim o estude e faça o seu próprio.
[]'s

giggs
(usa FreeBSD)

Enviado em 02/09/2012 - 13:17h

Pode ter ctza que tentarei entender o codigo e estudarei, caso contrario vou me ferrar nas provas. Obg.

paulo1205
(usa Ubuntu)

Enviado em 03/09/2012 - 02:02h

Nunca vi (nem consigo imaginar como fazer de modo que não seja artificiosamente complicado -- e inútil) uma implementação recursiva do crivo de Eratóstenes em C.

Googlando, só achei implementações razoáveis do crivo recursivo em linguagens funcionais, e o que as faz razoáveis é justamente uma forma de expressar-se que não tem contrapartida em linguagens estritamente procedurais e imperativas como o C -- a saber: listas com avaliação tardia e funções geradoras.