In quanti modi riusciamo a scrivere il crivello di Eratostene?

[Dino Del Favero]

On Mon, Nov 01, 2010 at 06:27:22PM +0100, Gianluca Moro wrote:
> ; Processo 1: produci il numero successivo (n->n+1)
> ; Processo 2: prendi il numero prodotto da processo 1, se e' multiplo di 2
> ;             eliminalo, altrimenti e' il prossimo numero primo
> ; Processo 3: prendi il numero prodotto da processo 2, se e' multiplo di 3
> ;             eliminalo, altrimenti e' il prossimo numero primo
> ;

Ciao,
prendendo spunto dal metodo esposto da Gianluca ho implementato la ricorsione
in C, il concetto non � lo stesso, ma molto simile (elimino il numero se � 
multiplo di un precedente)

dino@vanessa:~/BLUG>cat crivello_ric.c 
#include <stdio.h>

int primo(int *num, int *primoprec)
{
  if ((*num <= 2) || (*primoprec == 1))
    return 1;
  if ((*num % *primoprec) == 0)
    return 0;
  return (primo(num, --primoprec));
}

main (int argc, char **argv)
{
  if (argc == 1)
    printf("Uso: %s [limite_superiore]\n", argv[0]);
  else {
    int limite = atoi(argv[1]);
    int setaccio[limite], i, j;
    
    setaccio[0] = 1;
    setaccio[1] = 2;
    setaccio[2] = 3;

    for(i=2; setaccio[i] <= limite; )
      {
        if (primo(&(setaccio[i]), &(setaccio[i-1])))
          {
            setaccio[i+1] = setaccio[i] + 1;
            i++;
          }
        else
          setaccio[i]++;
      }
    
    for(j = 1; j < i; j++)
      printf("%d\n", setaccio[j]);
  }
}

dino@vanessa:~/BLUG>./crivello_ric 100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
dino@vanessa:~/BLUG>

Nulla di che, il C permette di giocare con i puntatori e a me piace :)
La cosa che vorrei far notare � che questo codice � molto molto meno 
performante di quello che avevo postato in precedenza!

dino@vanessa:~/BLUG>time ./crivello 100000
...
99971
99989
99991

real    0m0.374s
user    0m0.012s
sys     0m0.028s
dino@vanessa:~/BLUG>time ./crivello_ric 100000
...
99971
99989
99991

real    0m23.034s
user    0m20.905s
sys     0m0.112s
dino@vanessa:~/BLUG>

Nessun'altro ci prova? magari con altri linguaggi?

Saluti
Dino

-- 
   We cannot direct the wind, but we can adjust the sails.
Non possiamo dirigere il vento, ma possiamo regolare le vele.