Il Crivello di Eratostene in C

Il crivello di Eratostene è uno degli algoritmi più antichi e più efficienti per trovare tutti i numeri primi fino a un numero dato. Inventato dal matematico greco Eratostene di Cirene, questo algoritmo è ancora oggi fondamentale per la teoria dei numeri e ha applicazioni pratiche in vari campi dell'informatica e della crittografia. 

In questa pagina, esploreremo come implementare il crivello di Eratostene in linguaggio C, esaminando passo dopo passo i dettagli del codice.

Un numero primo è un numero naturale maggiore di 1 che ha esattamente due divisori distinti: 1 e se stesso. Ad esempio, i primi numeri primi sono 2, 3, 5, 7, 11, ecc.

Algoritmo del Crivello di Eratostene

L'algoritmo del crivello di Eratostene funziona eliminando i multipli dei numeri primi, lasciando solo i numeri primi. Ecco una descrizione del processo:

  1. Creare una lista di numeri da 2 a n.

  2. Iniziare dal primo numero primo, p (inizialmente 2).

  3. Eliminare tutti i multipli di p nella lista.

  4. Trovare il successivo numero non eliminato e ripetere il processo fino a √n.

  5. I numeri rimanenti nella lista sono tutti primi.

Implementazione in C

Ecco un esempio di implementazione del crivello di Eratostene in C:

#include <stdio.h> #include <stdlib.h> #include <math.h> // Funzione per eseguire il crivello di Eratostene void eratostene(int n) { // Allocazione dinamica di un array di booleani int *primo = malloc((n + 1) * sizeof(int)); if (primo == NULL) { fprintf(stderr, "Errore di allocazione della memoria\n"); return; } // Inizializzazione dell'array: consideriamo tutti i numeri come primi for (int i = 0; i <= n; i++) { primo[i] = 1; // 1 rappresenta "primo" } // Implementazione dell'algoritmo del crivello for (int p = 2; p <= sqrt(n); p++) { // Se primo[p] non è cambiato, è un numero primo if (primo[p] == 1) { // Aggiornamento di tutti i multipli di p come non primi for (int i = p * p; i <= n; i += p) { primo[i] = 0; // 0 rappresenta "non primo" } } } // Stampa dei numeri primi printf("Numeri primi fino a %d sono:\n", n); for (int p = 2; p <= n; p++) { if (primo[p] == 1) { printf("%d ", p); } } printf("\n"); // Libera la memoria allocata free(primo); } int main() { int n; // Input dall'utente printf("Inserisci un numero fino a cui trovare i numeri primi: "); scanf("%d", &n); // Chiamata alla funzione per il crivello di Eratostene eratostene(n); return 0; }

Complessità temporale e spaziale

L'algoritmo del crivello di Eratostene ha una complessità temporale di O(nlogn) e una complessità spaziale di O(n), rendendolo molto efficiente per trovare numeri primi fino a valori molto grandi di n.

Ottimizzazioni

Esistono diverse ottimizzazioni per il crivello di Eratostene, come l'uso di solo numeri dispari o l'eliminazione dei multipli dei numeri primi in modo più efficiente, ma queste possono aumentare la complessità del codice senza miglioramenti significativi per valori moderati di n.

Il crivello di Eratostene è un algoritmo classico ed efficiente per trovare numeri primi fino a un limite dato. Implementarlo in C è un eccellente esercizio per comprendere meglio la manipolazione degli array, l'allocazione dinamica della memoria e le operazioni matematiche di base.