Esercizio vettore numeri primi C

di il
26 risposte

Esercizio vettore numeri primi C

Buonasera, ho difficoltà a risolvere un esercizio che mi chiede:
calcolare i primi 30 numeri primi e inserirli in un vettore;
calcolare la media, il minimo e il massimo del vettore

scrivere una funzione per ogni operazione, cioè per il calcolo dei numeri primi, del massimo e del minimo.

Io sono riuscito a determinare i numeri primi però non attraverso l'utilizzo di funzione. Posto di seguito ciò a cui sono arrivato:

#include <stdio.h>
#define MAX 120
int main () {
int vett[MAX];
int j, k;
for (j=0;j<MAX; j++) {
vett[j]=0; // azzero tutti gli elementi del vettore
}

for (j=2; j<=MAX; j++) { // ora comincia il ciclo principale
if (vett[j]==1) continue ; // salto se il numero non e' primo
printf("%d ",j);
for (k=2*j; k<MAX; k+=j) { // escludo tutti i multipli di j
vett[k]=1;
}
}
for (j=2; j<MAX; j++) {
if (vett[j]==0) printf("%d ", j);
}
printf("\n");
return 0;
}
Potreste aiutarmi ? Grazie

26 Risposte

  • Re: Esercizio vettore numeri primi C

    Quello che hai implementato è noto come crivello di Eratostene, e permette di calcolare i numeri primi minori o uguali di un certo intero N (che nel tuo codice chiami MAX). Ma dal momento che l'esercizio chiede di calcolare i primi M (30 in questo caso) numeri primi, sorge spontanea una domanda:
    una volta fissato M, come fai a definire N?

    Per esempio nel tuo caso MAX potrebbe essere posto pari a 113, visto che il trentesimo numero primo è proprio 113.

    Per quanto riguarda il codice:
    - se poni MAX pari a 113, il tuo codice mi riporta come ultimo numero primo 109, il che non va bene se lo scopo è quello di implementare il crivello di Eratostene. Affinché sia analizzato anche il numero MAX (113 in questo caso) bisogna incrementare di uno la dimensione dell'array e sostituire i vari <MAX con <=MAX.
    - per inizializzare a 0 gli elementi di un array puoi anche scrivere v[DIM]={0};
    - l'ultimo ciclo for è inutile;
    - dal punto di vista logico il codice presenta ampi margini di ottimizzazione, se sei interessato fammi sapere che possiamo discuterne.

    Tralasciando per il momento le funzioni, che problemi incontri nel proseguire l'esercizio?
    - inserire i 30 numeri primi trovati in un vettore è banale;
    - il minimo e il massimo del vettore non vanno calcolati in quanto corrispondo rispettivamente al primo e all'ultimo elemento dello stesso;
    - per quanto riguarda la media come faresti?
  • Re: Esercizio vettore numeri primi C

    Si esatto , infatti ho posto per l’appunto MAX pari a 120 (sapendo che il 30esimo numero primo è 113, ma potevo anche mettere come dici tu lo stesso 113 sostituendo nei cicli for < con <=)

    Per quanto riguarda massimo e minimo appunto come dici tu non avrebbe senso calcolare il massimo e il minimo dato che rispettivamente corrispondo all’ultimo e al primo elemento del vettore , per questo mi suona strano.

    Invece per il calcolo della media scriverei una funzione dove dapprima mi calcolo la somma di tutti gli elementi e poi ovviamente dividerei per il numero di membri (in questo caso 30) , come vuole appunto la definizione di media.

    Grazie comunque per la disponibilità !
  • Re: Esercizio vettore numeri primi C

    Vedo che hai le idee abbastanza chiare, quindi qual è il problema? Nell'utilizzo delle funzioni?

    Questo è il tuo codice modificato in base agli aggiustamenti di cui parlavo al post precedente:
    #include <stdio.h>
    
    #define N 113
    
    int main()
    {
        int v[N + 1] = {0};
        unsigned int j;
        for(unsigned int i = 2; i <= N; ++i)
        {
            if(!v[i])
            {
                printf("%d\n", i);
                for(j = 2 * i; j <= N; j += i)
                {
                    v[j] = 1;
                }
            }
        }
        return 0;
    }
    Per quanto riguarda le ottimizzazioni, ti pongo due domande:
    - per i=7 è inutile far partire j da 14, infatti j può essere fatto partire tranquillamente da 49, mi sai dire perchè?
    - la variabile i assume valori che vanno da 2 a 113, ma sarebbe sufficiente arrivare a 11, perchè?
  • Re: Esercizio vettore numeri primi C

    Per il fatto che j possa partire da 49 è dovuto al fatto del crivello che mi dice che i numeri primi fino ad un certo numero N basta che controllo fino alla sua radice , quindi facendo un ragionamento inverso ipotizzerei 7^2=49 (l’ho pensata così)

    Per i che possa arrivare fino a 11 non riesco a capire il perché

    Comunque si il problema è l’uso di funzioni (più che altro appunto questa “stranezza del max e del min” e del calcolo della media)

    Ti ringrazio nuovamente !
  • Re: Esercizio vettore numeri primi C

    cls ha scritto:


    Per il fatto che j possa partire da 49 è dovuto al fatto del crivello che mi dice che i numeri primi fino ad un certo numero N basta che controllo fino alla sua radice , quindi facendo un ragionamento inverso ipotizzerei 7^2=49 (l’ho pensata così)
    Non so di preciso cosa dica il crivello, ma ragionando è facile intuire il motivo per cui j può essere fatto partire da i^2. La spiegazione consiste nel fatto che i multipli di i per i<i^2 sono sicuramente anche multipli di altri numeri primi minori di i. Per esempio nel caso di i=7, abbiamo che:
    - 14 è anche multiplo di 2;
    - 21 è anche multiplo di 3;
    - 28 è anche multiplo di 2;
    - 35 è anche multiplo di 5;
    - 42 è anche multiplo di 2 e 3.

    cls ha scritto:


    Per i che possa arrivare fino a 11 non riesco a capire il perché
    Il motivo è legato a quanto detto sopra. Per i=11, j dovrebbe partire da i^2=11^2=121, ma essendo 121>MAX=120, allora possiamo anche fermarci, in quanto siamo sicuri di aver già settato ad 1 tutti i numeri non primi minori di MAX.

    cls ha scritto:


    Comunque si il problema è l’uso di funzioni
    Il problema è di tipo "progettuale", ossia legato al fatto che non sai in che modo suddividere i vari compiti tra le funzioni, oppure è di carattere più pratico, nel senso che non conosci bene l'argomento "funzioni"?
    Prova a spiegarti meglio, altrimenti diventa difficile aiutarti.
  • Re: Esercizio vettore numeri primi C

    Ok per quanto riguarda i e j tutto chiaro. Credo che per analogia matematica fosse la stessa cosa però tu sei riuscito a spiegarla meglio ahah.

    Invece per quel che riguarda le funzioni (si hai ragione sono stato poco preciso io) è quello che hai detto per primo tu, cioè non so in che modo suddividere i vari compiti tra le funzioni. Per la media avevo pensato una cosa simile:
    
    float CalcolaMedia(float vett[], int n)
    {
        media = 0;
        for(i=0; i<n; i++)
            media = media + vett[i];
        media = media/n;
        return(media);
    }
    
    Per max e min io pensavo , appunto per il ragionamento fatto assieme, di non fare nessun calcolo ma indicare solamente che il max corrisponde all’ultimo elemento e il minimo al primo elemento.
  • Re: Esercizio vettore numeri primi C

    Il ragionamento sul massimo e sul minimo fila, però nell'esercizio sembra che ti chieda espressamente di fare delle funzioni per calcolarli, per quanto possa sembrare stupido farlo. Probabilmente è perché chi ha scritto il testo dell'esercizio vuole spingerti a far pratica col meccanismo di affidamento di compiti a funzioni...

    Ipotesi, eh!

    Ps. Se in una parte del programma usi un vettore int v[] e devi poi lavorarci sopra, non ha molto senso fare una funzione float CalcolaMedia(float vett[], int n). Se inizi con int, mantieni int, no? Perché passare a float (che poi il compilatore si lamenta)?
  • Re: Esercizio vettore numeri primi C

    Ciao AldoBaldo , si hai ragione però ho utilizzato float perché il valore della media può essere benissimo un numero decimale , per questo.
    La tua ipotesi comunque può essere idonea , bisogna solo capire se fare una funzione con il conto alla mano o semplicemente un’indicazione al primo e all’ultimo elemento
  • Re: Esercizio vettore numeri primi C

    Ciao AldoBaldo , si hai ragione però ho utilizzato float perché il valore della media può essere benissimo un numero decimale , per questo.
    Credo che AldoBaldo non si riferiva al tipo di ritorno della funzione, ma al tipo dell'array.
    In ogni caso affinché il valore di ritorno sia un numero decimale puoi tranquillamente definire una variabile intera somma (in cui andrai a sommare tutti gli elementi dell'array) e scrivere alla fine return (float)somma/n (operazione di casting esplicito per evitare che il quoziente sia calcolato come divisione intera).
    La tua ipotesi comunque può essere idonea , bisogna solo capire se fare una funzione con il conto alla mano o semplicemente un’indicazione al primo e all’ultimo elemento
    Sinceramente non mi soffermerei troppo su queste cose... se vuoi implementare una generica funzione che ritorna il massimo o il minimo di un array (per quanto inutile in questo caso) sei libero di farlo.
  • Re: Esercizio vettore numeri primi C

    Giusto, però se hai degli int nell'array nella funzione "d'origine", credo proprio che dovresti anche avere un puntatore a int tra i parametri della funzione di calcolo della media. Ciò non toglie che potresti poi restituire un float come valore di ritorno, tipo: float CalcolaMedia(const int *vett, int n). A quel punto, la funzione potrebbe diventare così...
    float CalcolaMedia( const int *vett, int n ) {
        int i, somma;
        
        for( somma=0, i=0; i<n; i++ )
            somma += vett[i];
            
        return ((float)somma)/((float)n);
    }
    In merito al tipo di calcolo da effettuare nelle altre due funzioni (ovvero se effettuarlo concretamente o limitarsi a restituire il primo e l'ultimo valore), non sono certo nella testa di chi ha scritto l'esercizio, però dovessi consegnarlo io farei una di tre cose:

    1. se possibile, chiedere lumi all'insegnante o, almeno, consultarsi con qualche compagno per sondare le possibili intenzioni del testo
    2. se 1. non è praticabile, seguire la strada più completa, specificando magari in un commento per l'insegnante le ragioni (spiccatamente scolastiche) per le quali si è scelta una soluzione apparentemente meno efficace
    3. seguire la strada più completa, mentendo spudoratamente nell'affermare che si è scelta quella strada per attribuire maggiore genericità alle funzioni, onde renderle più versatili in previsione di un riutilizzo in occasioni future
  • Re: Esercizio vettore numeri primi C

    Vedo che Nippolo ha risposto mentre stavo scrivendo. Scusate il doppione.
  • Re: Esercizio vettore numeri primi C

    Buongiorno ad entrambi, si appena vedrò il professore chiederò un parere riguardo le funzioni di max e min.

    Ma se volessi scrivere una funzione riguardo al calcolo dei primi 30 numeri primi ? Come dovrei fare ? Sempre un'operazione simile a come è stato fatto nel main ?
  • Re: Esercizio vettore numeri primi C

    In effetti non cambia niente. La soluzione più semplice credo sia creare una funzione che riceva un puntatore a un array (dichiarato nella funzione chiamante) da usare come "contenitore" per i numeri generati e un valore che specifichi quanti numeri primi si vuole che vengano generati. Tipo...

    void GeneraPrimi( int *v, unsigned int qPrimi );

    A quel punto puoi spostare nel corpo di GeneraPrimi() il codice che hai già preparato.
  • Re: Esercizio vettore numeri primi C

    Dunque praticamente verrebbe così:
    
    void GeneraPrimi( int *v, unsigned int qPrimi ) {
    unsigned int j;
        for(unsigned int i = 2; i <= N; ++i)
        {
            if(!v[i])
            {
                printf("%d\n", i);
                for(j = 2 * i; j <= N; j += i)
                {
                    v[j] = 1;
                }
            }
        }
        
    }
    
Devi accedere o registrarti per scrivere nel forum
26 risposte