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.

Numeri Primi

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.

Conclusione

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.

Indice pagine linguaggio C: