[C] - Crivello di Eratostene

g@lil3o

il 09 feb 2021, 19:02

9 risposte

g@lil3o

Pochi posts

Iscritto da: nov, 2019

Messaggi:: 43

[C] - Crivello di Eratostene

09 feb 2021, 19:29

Salve a tutti, vorrei un parere sul seguente esercizio:

ES: Il Crivello di Eratostene è un metodo per trovare i numeri primi. Esso funziona come segue:

1) Create un vettore con tutti gli elementi inizializzati a 1 (vero). Gli elementi del vettore i cui indici corrispondano a un numero primo resteranno a 1. Al termine della elaborazione, tutti gli altri elementi del vettore saranno azzerati.

2) Partendo dall'indice 2 del vettore (l'indice 1 è primo per definizione), qualora il valore dell'elemento puntato sia 1, scorrete il resto del vettore e azzerate gli elementi i cui indici siano multipli di quello dell'elemento puntato. Nel caso dell'indice 2, saranno azzerati tutti gli elementi successivi del vettore con indici che siano multipli di 2 (ovverosia gli indici 4, 6, 8, 10 ecc.). Nel caso dell'indice 3, saranno azzerati tutti gli elementi successivi del vettore con indici che siano multipli di 3 (ovverosia gli indici 6, 9, 12, 15 ecc.).

Nel momento in cui questo processo sarà stato completato, gli elementi del vettore che conterranno ancora il valore 1 indicheranno che il loro indice è un numero primo e, di conseguenza, che potrà essere visualizzato. Scrivete un programma che utilizzi un vettore di 1000 elementi per determinare e visualizzare i numeri primi compresi tra 1 e 999. Ignorate l'elemento 0 del vettore.

Io l'ho svolto in questo modo:

#include <stdio.h>
#define DIM 1000

void eratostene(int vett[], int i);

int main()
{
    int vettore[DIM], i;

    printf("\n");

    for(i = 0; i < DIM; i++)
        vettore[i] = 1;
    
    for(i = 2; i < DIM; i++)
        eratostene(vettore, i);

    for(i = 2; i < DIM; i++)
    {
        if(vettore[i] != 0)
            printf("%d ", i);
    }

    printf("\n\n");
    return 0;
} 

void eratostene(int vett[], int i)
{   
    int y;
    if(vett[i] == 1)
    {
        for(y = i + i; y < DIM; y = y + i)
            vett[y] = 0;
    }
}

Secondo voi è corretto o va corretto qualcosa?

Grazie

9 Risposte

Andrea Quaglia
Molto attivo
Iscritto da
giu, 2017
Messaggi:
603
Re: [C] - Crivello di Eratostene
09 feb 2021, 21:57
Se compila e l'output è corretto, allora il programma va bene.
Se invece ti stai chiedendo se c'erano altre strade per arrivare al risultato, la risposta è si, non era nemmeno necessario fare una funzione dedicata.
Weierstrass
Utente Famoso
Iscritto da
feb, 2019
Messaggi:
2246
Re: [C] - Crivello di Eratostene
09 feb 2021, 22:01
Sì è corretto. Potevi semplificare
```
   int vettore[DIM] = {0}, i;

   printf("\n");
   
   for(i = 3; i < DIM; i+=2)
       vettore[i] = 1;
    
   for(i = 3; i * i < DIM; i+=2)
        eratostene(vettore, i);
```
Come dice Andrea è meglio non fare la funzione dedicata, che sui numeri grossi si vede la differenza

g@lil3o

Pochi posts

Iscritto da: nov, 2019

Messaggi:: 43

Re: [C] - Crivello di Eratostene

10 feb 2021, 11:48

Grazie dei suggerimenti, ho provato a svolgerlo senza utilizzare una funzione dedicata ed eliminando un ciclo for:

#include <stdio.h>
#define DIM 1000

int main()
{
    int vettore[DIM] = {0}, i, j;

    printf("\n");

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

meglio così?

Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1237
Re: [C] - Crivello di Eratostene
10 feb 2021, 12:06
Alcune considerazioni:
- perché non dichiari le variabili i e j direttamente all'interno dei for?
- invertendo l'utilizzo di 0 e 1 puoi eliminare un ulteriore ciclo for;
- la variabile j può anche essere inizializzata a i*i, in quanto tutti i multipli di i minori di i*i a quel punto saranno ovviamente già stati considerati.

In definitiva si avrebbe qualcosa del genere:
```
#include <stdio.h>

#define DIM 1000

int main()
{
    int v[DIM] = {0};
    for(int i = 2; i < DIM; ++i)
    {
        if(!v[i])
        {
            printf("%d ", i);
            for(int j = i * i; j < DIM; j += i)
            {
                v[j] = 1;
            }
        }
    }
    return 0;
}
```
g@lil3o
Pochi posts
Iscritto da
nov, 2019
Messaggi:
43
Re: [C] - Crivello di Eratostene
10 feb 2021, 15:28
Nippolo ha scritto:
Alcune considerazioni:
- perché non dichiari le variabili i e j direttamente all'interno dei for?
- invertendo l'utilizzo di 0 e 1 puoi eliminare un ulteriore ciclo for;
- la variabile j può anche essere inizializzata a i*i, in quanto tutti i multipli di i minori di i*i a quel punto saranno ovviamente già stati considerati.

In definitiva si avrebbe qualcosa del genere:
#include <stdio.h> #define DIM 1000 int main() { int v[DIM] = {0}; for(int i = 2; i < DIM; ++i) { if(!v[i]) { printf("%d ", i); for(int j = i * i; j < DIM; j += i) { v[j] = 1; } } } return 0; }
Sulle tue considerazioni avrei alcune domande :

1) dichiarare le variabili direttamente nei for è solo una scelta di stile o in qualche modo migliora le prestazioni?
2) sulla seconda ok, in sostanza elimino il for con cui assegno il valore 1 ad ogni elemento del vettore, giusto?
3) in effetti tutti i multipli prima di i*i sono già stati controllati e quindi scarto operazioni inutili.

Un'ultima cosa, ho provato ad eseguire il tuo codice su un input di 1000000 ma durante l'esecuzione mi da un segmentation fault che credo dipenda dalla dimensione int, ho risolto utilizzando un unsigned int per i e j ma non so se sia corretto.

grazie

Weierstrass

Utente Famoso

Iscritto da: feb, 2019

Messaggi:: 2246

Re: [C] - Crivello di Eratostene

10 feb 2021, 17:02

Il tipo dentro il for si può fare dal C99, prima no. Se metti il compilatore C89 ti dà errore. Comunque sono passati più di 20 anni, quindi sarebbe anche ora di dare la feature per acquisita

Per il segmentation fault prova così


#include <stdio.h>
#include <inttypes.h>

#define DIM 10000000

uint32_t v[DIM];

int main()
{
    uint32_t n = 0;
    for(uint32_t i = 2; i < DIM; ++i)
    {
        if(!v[i])
        {
            printf("%7u ", i);
            n++;
            if(n > 9)
            {
                printf("\n");
                n = 0;
            }
            for(uint32_t j = i * i; j < DIM; j += i)
            {
                v[j] = 1;
            }
        }
    }
    return 0;
}

Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1237
Re: [C] - Crivello di Eratostene
10 feb 2021, 19:05
g@lil3o ha scritto:
1) dichiarare le variabili direttamente nei for è solo una scelta di stile o in qualche modo migliora le prestazioni?
Ridurre al minimo lo scope (la visibilità) di una variabile comporta vari vantaggi riguardanti innanzitutto la chiarezza e la leggibilità del codice.
g@lil3o ha scritto:
2) sulla seconda ok, in sostanza elimino il for con cui assegno il valore 1 ad ogni elemento del vettore, giusto?
Esatto, in pratica alla fine i numeri primi saranno quelli contrassegnati dallo 0.
g@lil3o ha scritto:
Un'ultima cosa, ho provato ad eseguire il tuo codice su un input di 1000000 ma durante l'esecuzione mi da un segmentation fault che credo dipenda dalla dimensione int, ho risolto utilizzando un unsigned int per i e j ma non so se sia corretto.
Per scongiurare eventuali overflow nei calcoli (in particolare mi riferisco a j=i*i), e quindi accessi a zone di memoria non allocate, basta utilizzare la condizione
```
i < DIM / i
```
che peraltro costituisce anche un ulteriore ottimizzazione in quanto andando oltre l'array non subirà alcuna ulteriore modifica.

Un altro problema potrebbe essere la dimensione dell'array, quindi per esso ti consiglio il tipo intero più piccolo (8 bit).

In definitiva, anche se può risultare un po' ridondante, il massimo dell'efficienza dovrebbe coincidere con qualcosa del genere:
```
#include <stdio.h>
#include <stdint.h>

#define DIM 1000

int main()
{
    int8_t v[DIM] = {0};
    unsigned int i;
    for(i = 2; i < DIM / i; ++i)
    {
        if(!v[i])
        {
            printf("%u\t", i);
            for(unsigned int j = i * i; j < DIM; j += i)
            {
                ++v[j];
            }
        }
    }
    for(; i < DIM; ++i)
    {
        if(!v[i])
        {
            printf("%u\t", i);
        }
    }
    return 0;
}
```
g@lil3o
Pochi posts
Iscritto da
nov, 2019
Messaggi:
43
Re: [C] - Crivello di Eratostene
11 feb 2021, 19:06
Weierstrass ha scritto:
Il tipo dentro il for si può fare dal C99, prima no. Se metti il compilatore C89 ti dà errore. Comunque sono passati più di 20 anni, quindi sarebbe anche ora di dare la feature per acquisita

Per il segmentation fault prova così

#include <stdio.h> #include <inttypes.h> #define DIM 10000000 uint32_t v[DIM]; int main() { uint32_t n = 0; for(uint32_t i = 2; i < DIM; ++i) { if(!v[i]) { printf("%7u ", i); n++; if(n > 9) { printf("\n"); n = 0; } for(uint32_t j = i * i; j < DIM; j += i) { v[j] = 1; } } } return 0; }
no no utilizzo C99 era solo una mia curiosità sulle prestazioni, per quanto riguarda il segmentation fault non avevo mai usato la libreria
```
inttypes.h
```
...molto utile, grazie
g@lil3o
Pochi posts
Iscritto da
nov, 2019
Messaggi:
43
Re: [C] - Crivello di Eratostene
11 feb 2021, 19:07
Nippolo ha scritto:

g@lil3o ha scritto:
1) dichiarare le variabili direttamente nei for è solo una scelta di stile o in qualche modo migliora le prestazioni?
Ridurre al minimo lo scope (la visibilità) di una variabile comporta vari vantaggi riguardanti innanzitutto la chiarezza e la leggibilità del codice.
g@lil3o ha scritto:
2) sulla seconda ok, in sostanza elimino il for con cui assegno il valore 1 ad ogni elemento del vettore, giusto?
Esatto, in pratica alla fine i numeri primi saranno quelli contrassegnati dallo 0.
g@lil3o ha scritto:
Un'ultima cosa, ho provato ad eseguire il tuo codice su un input di 1000000 ma durante l'esecuzione mi da un segmentation fault che credo dipenda dalla dimensione int, ho risolto utilizzando un unsigned int per i e j ma non so se sia corretto.
Per scongiurare eventuali overflow nei calcoli (in particolare mi riferisco a j=i*i), e quindi accessi a zone di memoria non allocate, basta utilizzare la condizione
i < DIM / i
che peraltro costituisce anche un ulteriore ottimizzazione in quanto andando oltre l'array non subirà alcuna ulteriore modifica.

Un altro problema potrebbe essere la dimensione dell'array, quindi per esso ti consiglio il tipo intero più piccolo (8 bit).

In definitiva, anche se può risultare un po' ridondante, il massimo dell'efficienza dovrebbe coincidere con qualcosa del genere:
#include <stdio.h> #include <stdint.h> #define DIM 1000 int main() { int8_t v[DIM] = {0}; unsigned int i; for(i = 2; i < DIM / i; ++i) { if(!v[i]) { printf("%u\t", i); for(unsigned int j = i * i; j < DIM; j += i) { ++v[j]; } } } for(; i < DIM; ++i) { if(!v[i]) { printf("%u\t", i); } } return 0; }
Chiarissimo, grazie mille

Devi accedere o registrarti per scrivere nel forum

9 risposte