Edizione didattica italiana

Crivello di Eratostene in C

Trova i numeri primi fino a N marcando i multipli dei candidati.

Crea un array di candidati da 0 a N ed escludi 0 e 1. Per ogni primo p marca i suoi multipli. Inizia da p * p: i multipli precedenti hanno già un fattore più piccolo.

Basta iniziare la marcatura per p fino alla radice di N. Evita overflow di p * p con limiti grandi, per esempio usando p <= N / p per p positivo. Il buffer deve includere la posizione N.

Il crivello classico usa O(N) memoria e circa O(N log log N) tempo. Prova 0, 1, 2 e un limite maggiore, adattando il programma quando necessario.

Codice sorgente

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

void sieve(int n) {
    bool isPrime[n + 1];
    memset(isPrime, true, sizeof(isPrime));

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    printf("Primes up to %d:\n", n);
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) printf("%d ", p);
    }
    printf("\n");
}

int main() {
    int n = 50;
    sieve(n);
    return 0;
}

Apri nel compilatore

Risultato atteso

Primes up to 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Domande frequenti

Perché il codice e alcuni risultati restano in inglese?

Parole chiave C, identificatori, commenti del programma e output attesi restano quelli originali per preservare codice eseguibile e test coerenti. Spiegazioni e istruzioni sono tradotte.