Il crivello di Eratostene è un algoritmo, piuttosto antico, per il calcolo dei numeri primi. L’ideatore del crivello è stato il matematico Eratostene di Cirene da cui appunto deriva il nome.
Essendo un metodo piuttosto semplice, viene spesso implementato in molti linguaggi di programmazione a scopo didattico.
In questa lezione proponiamo il crivello di Eratostene in linguaggio C, sviluppato con le funzioni e gli array.
Metodo del crivello di Eratostene
Il metodo per trovare i numeri primi consiste nello scrivere i numeri naturali da 2 fino ad n. Dopo si cancellano tutti i multipli del primo numero, poi quelli del secondo e così via.
Adesso prendiamo il numero successivo alla lista che è il numero 3 e togliamo quindi tutti i multipli di 3:
2, 3, 5, 7, 9, 11, 13, 15, 17, 19
E così via, ma non essendoci più multipli, i numeri restanti sono:
2, 3, 5, 7, 11, 13, 17, 19
Quindi ecco i numeri primi da 2 a 20.
Sviluppo del crivello di Eratostene in linguaggio C
Implementiamo il crivello con un programma in C. Vi presento sotto il listato e poi vi spiego l’algoritmo passo passo.
Ecco dunque il listato completo del crivello di Eratostene:
#include <stdio.h>
#define N 1000
int insert(int *v) {
int i, n;
printf("Quanti numeri n: ");
scanf("%d", &n);
/*generiamo un vettore con tutti i numeri 0 dove l'indice i va da 2 ad n*/
for(i=2; i<=n; i++)
v[i]=0;
return n;
}
void eratostene(int *v, int n) {
int i,j;
for(i=2; i<=n; i++)
if(v[i]==0) //se l'elemento v[i] è zero
for(j=2*i; j<=n; j+=i)
//imposto v[j] a 1, cioè escludo i suoi multipli
v[j]=1;
}
void print(int *v, int n) {
int i;
for(i=2; i<=n; i++)
if(v[i]==0) //se il numero è primo
printf("%d\t",i); //stampo i risultati
}
int main() {
int a[N],n;
n=insert(a);
eratostene(a,n);
print(a,n);
return 0;
}
Per implementare l’algoritmo del crivello di Eratostene quindi faremo uso dei vettori e delle funzioni (potevo anche farne a meno, ma volevo consolidarne l’uso).
Quindi chiediamo quanto deve essere n, ovvero fino a quale numero calcolare i numeri primi e con un ciclo for inizializziamo l’array con tutti i numeri 0.
L’array avrà l’indice che va da 2 a n.
Adesso dobbiamo trovare i numeri primi e per farlo prendiamo in considerazione il primo numero con indice 2. Controlliamo se ci sono multipli di 2 e se vero settiamo l’elemento a 1.
dato che j<=n, cioè 4<=20 è vera, continuiamo il ciclo interno.
for(j=2*i; j<=n; j+=i) j=6 v[j]=1; v[6]=1;
dato che j<=n, cioè 6<=20 è vera, continuiamo il ciclo interno.
j=j+i cioè j=6+2=8
procediamo analogamente per gli altri numeri e quindi: v[8]=1, v[10]=1, v[12]=1, v[14]=1, v[16]=1, v[18]=1, v[20]=1 in questo caso avremo che il passo successivo è j=j+2, cioè j=22 e la condizione j<=n non è più verificata. Pertanto si procede ad incrementare i dal ciclo più esterno.
Adesso dunque i=3
for(i=2; i<=n; i++) i=3 if(v[i]==0) vero for(j=2*i; j<=n; j+=i)j=6 v[j]=1; v[6]=1; //in realtà già era stata calcolato
j=j+i cioè j=6+3=9
dato che j<=n, cioè 9<=20 è vera continuiamo il ciclo interno.
for(j=2*i; j<=n; j+=i) j=9 v[j]=1;v[9]=1;
dato che j<=n, cioè 9<=20 è vera continuiamo il ciclo interno.
j=j+i cioè j=9+3=12
procediamo analogamente per gli altri numeri e quindi: v[12]=1, v[15]=1, v[18]=1 in questo caso avremo che il passo successivo è j=j+3, cioè j=21 e la condizione j<=n non è più verificata. Pertanto si procede ad incrementare i dal ciclo più esterno.
Si procede dunque con i=4 ma in questo caso if(v[i]==0) risulta falsa in quanto avevamo impostato v[4]=1; quindi si incrementa nuovamente i che diventa 5 e si procede con lo stesso ragionamento di prima.
Al termine quelli rimasti sono i numeri primi e li stampiamo semplicemente con queste istruzioni:
for(i=2; i<=n; i++) if(v[i]==0) //se il numero è primo printf(“%d\t”,i); //stampo i risultati
Cioè scorriamo tutto l’array, se l’elemento contenuto in esso è zero, vuol dire che il numero è primo, dunque stampo l’indice.
Notiamo anche che, se volessimo invece stampare tutti i numeri non primi, basterebbe impostare:
for(i=2; i<=n; i++)
if(v[i]==1) //se il numero non è primo
printf("%d\t",i); //stampo i risultati
Questo è solo un possibile esempio di come impostare l’algoritmo che rappresenta il calcolo dei numeri primi con il crivello di Eratostene.
Creiamo altri esempi di funzioni che generano array random in C.
Primo esempio di array random con le funzioni in C
Sviluppare un programma che genera e visualizza due array random tramite l’uso di funzioni. Dunque creare una funzione che generi i due array e una funzione che li visualizzi.
Quindi iniziamo creando la nostra funzione random_array, che riceve un array passato per indirizzo. Questa funzione genera un array di numeri random compresi tra 1 e 10 e restituisce un intero, il numero degli elementi.
Dopo creiamo la funzione print che stampa un array. Questa funzione ha come parametri formali la dimensione dell’array e l’array passato per indirizzo e non restituisce nulla.
Successivamente nel main dichiariamo i due vettori a e b e le due dimensioni n1 ed n2. Dopo invochiamo le funzioni random_array e print.
Ecco dunque il listato completo di array random con le funzioni in C.
#include <stdio.h>
#include <time.h>
#define N 10
int random_array(int *v1) {
int i, n;
srand((unsigned) time(NULL));
do {
printf("Quanti elementi?: ");
scanf("%d", &n);
} while (n<0 || n>N);
for (i=0; i<n; i++)
v1[i] = rand()%10+1;
return n;
}
void stampa_array(int n, int v[]) {
int i;
for (i=0; i<n; i++) {
printf("%d\n", v[i]);
}
}
int main(void) {
int n1, n2, a[N], b[N];
n1 = random_array(a);
stampa_array(n1, a);
printf("\n");
n2 = random_array(b);
stampa_array(n2, b);
return 0;
}
Secondo esempio di array random con le funzioni in C
Realizziamo un secondo esempio, sempre con i numeri random.
Sviluppare un programma che genera e visualizza due array random tramite l’uso di funzioni. Sommare i due array e visualizzare un nuovo array che contiene la somma di ciascun elemento.
In pratica dati due array ad esempio a[5] e b[5], l’array c[5] sarà così composto:
c[0]=a[0]+b[0]; e così via.
Creiamo dunque una funzione sum che prende come parametri formali i due array passati per indirizzo. La funzione è molto semplice da implementare, infatti con un semplice ciclo si sommano gli elementi: c[i] = a[i] + b[i].
#include <stdio.h>
#include <time.h>
#define N 10
void random_array(int *v) {
int i;
srand((unsigned) time(NULL));
for (i=0; i<N; i++)
v[i] = rand()%10+1;
}
void *sum(int *a, int *b){
int i, *c;
for(i=0; i<N; i++) {
c[i] = a[i] + b[i]; //somma gli elementi dei due vettori
printf("%d\t", c[i]);
}
}
void stampa_array(int *v) {
int i;
for (i=0; i<N; i++) {
printf("%d\t", v[i]);
}
}
int main(void) {
int i, a[N], b[N];
char invio;
printf("\nGenero il primo array: ");
random_array(a);
stampa_array(a);
printf("\n\nInvio per generare il secondo array");
scanf("%c", &invio);
printf("\nGenero il secondo array: ");
random_array(b);
stampa_array(b);
printf("\n\nLa somma dei due array: ");
sum(a,b);
return 0;
}
In questa lezione continueremo a studiare alcuni esempi di passaggio di array a funzioni, al fine di consolidare l’argomento.
Primo esempio di passaggio di array a funzioni
Quindi realizziamo un semplice programma che sviluppi due funzioni: insert che permette di inserire i dati in un array e print che invece permette di stampare i dati di un array.
In questo esempio non utilizzeremo i prototipi, ma inseriremo prima le definizioni delle funzioni insert e print, semplicemente per proporre una modalità differente da quella precedente.
La prima funzione che definiremo è dunque insert che con un semplice ciclo for permetterà l’inserimento di tutti gli elementi di un vettore v[] che è stato passato per indirizzo alla funzione.
Allo stesso modo costruiamo la funzione print.
Dopo nel main invochiamo semplicemente le nostre funzioni.
Ecco dunque il listato completo dell’esempio di passaggio di array a funzioni.
#include <stdio.h>
#define N 10
void insert(int v[]) {
int i;
for (i<0;i<N;i++) {
printf("inserisci elemento %d: ", i+1);
scanf("%d", &v[i]);
}
}
void print(int v[]) {
int i;
for (i=0; i<N; i++)
printf("%d\t", v[i]);
}
int main() {
int a[N];
insert(a);
print(a);
return 0;
}
Secondo esempio di passaggio di array a funzioni
Proviamo a variare l’esercizio precedente chiedendo quanti elementi inserire in un vettore.
Inoltre utilizziamo int *v, al posto di int v[] che come dicevamo nella precedente lezione sono due metodi equivalenti.
Sviluppiamo quindi la nostra funzione insert che questa volta, al contrario di prima, ci dovrà ritornare il numero degli elementi inseriti (n). Facciamo anche un controllo dell’input su quanti elementi inserire nell’array.
La funzione print avrà come parametri formali l’array passato per indirizzo e il numero degli elementi (n).
Ecco dunque il listato completo di un altro esempio di passaggio di array a funzioni.
#include <stdio.h>
#define N 100
int insert(int *v) { //è uguale a int v[]
int i, n;
do {
printf("Quanti elementi?");
scanf("%d", &n);
} while (n<0 || n>N);
for (i<0;i<n;i++) {
printf("inserisci elemento %d: ", i+1);
scanf("%d", &v[i]);
}
return n;
}
void print(int *v, int n) {
int i;
for (i=0; i<n; i++)
printf("%d\t", v[i]);
}
int main() {
int a[N], n;
n=insert(a);
/*attenzione chiaramente cambia anche l'invocazione della funzione, insert infatti restituisce un intero, il numero degli elementi*/
print(a, n);
return 0;
}
Chiaramente questi sono solo degli esempi molto semplici di passaggio di array a funzioni, nella prossima lezione ne faremo degli altri.
Commenti recenti