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.