Crivello di Eratostene

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.

Facciamo un esempio con n=20. Avremo:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Iniziamo cancellando tutti i multipli di 2, evidenziandoli di rosso:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Quindi ecco i numeri rimasti:

2, 3, 5, 7, 9, 11, 13, 15, 17, 19

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.

Agiamo dunque così:

for(i=2; i<=n; i++)              i=2
    if(v[i]==0)                        vero
       for(j=2*i; j<=n; j+=i)    j=4
           v[j]=1;                        v[4]=1; 

j=j+i cioè j=4+2=6

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.

Alcuni link utili

Realizzare un menù di scelta in C

Strutture complesse in C

Esercizio sulle struct in C

Typedef struct C

Somma elementi diagonale principale di una matrice

Come sommare gli elementi della cornice esterna

Come sommare due matrici

Matrice trasposta

Prodotto tra matrici

Ricerca elementi in una matrice

Quali metodi per inserire dati in una matrice

Tavola pitagorica in C

Array multidimensionali

Quick sort in C

Selection sort in C

Merge sort in C

Insertion Sort in C


Autore dell'articolo: cristina

Avatar per Coding Creativo

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *