[C]Ottimizzazione crivello Eratostene

[ilario991]

Ho realizzato il seguente programma in c per calcolare i numeri primi minori di N.

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

int main(){
    int N, *vettore,i;
    printf("Inserisci numero fino a cui vuoi calcolare numeri primi: ");
    scanf("%d",&N);
    N--;
    vettore=(int *)malloc(sizeof(int)*N);
    for(i=0;i<N;i++) vettore[i]=i+1;
    for(i=3;i<N;i+=2) vettore[i]=0;
    for(i=5;i<N;i+=3) vettore[i]=0;
    for(i=9;i<N;i+=5) vettore[i]=0;
    for(i=13;i<N;i+=7) vettore[i]=0;
    for(i=0;i<N;i++)
    if(vettore[i]!=0)
     printf("%d ",vettore[i]);
    free(vettore);
    getch();
}

Ho cercato questo algoritmo su internet, ed ho visto che è diverso(praticamente nessuno è uguale al mio). Ho visto anche quello su wikipedia, ma nn l'ho capito tanto(usa funzioni che io non so ancora usare). Mi potete aiutare ad ottimizzare il mio algoritmo?

[apatriarca]

Non è questione di ottimizzare il codice ma di correggerlo. Il tuo codice non funziona. Elimini dall'array tutti i multipli dei primi numeri primi, ma i multipli degli altri?

[ilario991]

L'algoritmo per funzionare funziona, ho confrontato i risultati con quelli su wikipedia... Poi ho capito che l'algoritmo di Eratostene fa proprio qst, cmq mi puoi aiutare???

[apatriarca]

Ho compilato il tuo programma (dopo aver tolto getch che non è standard e non viene riconosciuta dal mio compilatore).

I numeri in grassetto non sono numeri primi:

Inserisci numero fino a cui vuoi calcolare numeri primi: 200
1 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 101 103
107 109 113 121 127 131 137 139 143 149 151 157 163 167 169 173 179 181 187 191
193 197 199

Il numero di numeri non primi trovati dal tuo codice aumentano con l'aumentare del limite. Il tuo codice non è quindi corretto. Per essere corretto dovresti cancellare tutti i multipli dei numeri primi minori o uguali alla radice quadrata del numero. Ti consiglio di rileggerti bene la descrizione dell'algoritmo e implementarlo in modo corretto prima di provare ad ottimizzarlo.

[ilario991]

mmm, ok, allora a qst punto nn saprei come fare, puoi darmi qualche idea? Ho letto diversi codici su internet, xò nn li ho capiti...

[apatriarca]

Che cosa non ti è chiaro esattamente? Hai provato a leggere la descrizione dell'algoritmo in pseudocodice?

[ilario991]

No, su internet nn la trovo da nessuna parte, cavolo!!!
Ho trovato questo:

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

#define MAX 100

int main(void) {
  int v[MAX], i, j;

  for (i=2; i<MAX; i++)
    v[i] = 1;
  for (i=2; i<MAX; i++) {
    if (v[i] == 1) {
      printf("%d ", i);
      for (j=2; i*j<MAX; j++)
        v[i*j] = 0;
    }
  }
  printf("\n");
  return(1);
}

Allora, non ho capito:
for (i=2; i if (v == 1) {
printf("%d ", i);
for (j=2; i*j v[i*j] = 0;//IDEM
Cmq puoi indicarmi dove posso trovarlo in pseudolinguaggio???x favore, è urgente!!!

[apatriarca]

Arriva fino a MAX invece che alla sua radice quadrata perché visualizza i numeri primi mentre li calcola. Un modo migliore (più efficiente) sarebbe quello di calcolarli e poi visualizzarli (oppure quello di ottimizzare il ciclo interno come spiego in seguito). Il ciclo più interno calcola semplicemente tutti i multipli del numero primo minori di MAX e li segna come non primi. È in realtà possibile ottimizzare questo ciclo partendo dal suo quadrato (tutti i suoi multipli minori del suo quadrato sono multipli di un primo minore di lui). Il codice ottimizzato (e leggermente modificato per mostrare alcune cose) è il seguente:

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

/* un modo alternativo di definire costanti. */
enum {MAX = 200};

int main()
{
    int v[MAX], i, j;

    for (i = 2; i < MAX; ++i) v[i] = 1;

    for (i = 2; i < MAX; ++i) {
        if (v[i] == 1) {
            printf("%d ", i);

            for (j = i*i; j < MAX; j += i) v[j] = 0;
        }
    }

    /* è più efficiente di printf per stampare stringhe (va a capo in modo automatico e quindi ho inserito due a capo...) */
    puts("\n");

    return 0; /* <- è 0 che si restituisce quando è andato tutto bene... */
}