Programmazione.it :: Il crivello di Eratostene

Il crivello di Eratostene

Scritto da Fabrizio Furnari il 07-11-2007 ore 08:44

Circa 200 anni prima della nascita di Cristo un matematico alessandrino, ma originario di Cirene, svela al mondo un algoritmo — uno dei primi della storia — per l'individuazione dei numeri primi. Il nome del poeta, geografo, astronomo e matematico cirenaico è, come molti avranno già intuito, Eratostene, e l'algoritmo è detto "crivello" ovvero setaccio, per la particolarità del metodo usato. E' un algoritmo semplice e sicuramente bisognoso di miglioramenti, ma ha il pregio di poter essere implementato facilmente con vari linguaggi di programmazione.

Wikipedia ne mostra una versione in pseudo-codice, mentre la versione in Java che riporto di seguito è tratta dalla Rete. Esaminiamo innanzitutto il codice, per poi spiegare come funziona l’algoritmo:

<span style="font-size:1.0em">
public class PrimeSieve {
    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);
 
        // initially assume all integers are prime
        boolean[] isPrime = new boolean[N + 1];
        for (int i = 2; i <= N; i++) {
            isPrime[ i ] = true;
        }
 
        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i*i <= N; i++) {
 
            // if i is prime, then mark multiples of i as nonprime
            // suffices to consider mutiples i, i+1, ..., N/i
            if (isPrime[ i ]) {
                for (int j = i; i*j <= N; j++) {
                    isPrime[ i * j ] = false;
                }
            }
        }
 
        // count primes
        int primes = 0;
        for (int i = 2; i <= N; i++) {
            if (isPrime[ i ]) primes++;
        }
        System.out.println("The number of primes <= " + N + " is " + primes);
</span>

Il listato qui sopra non fa altro che “setacciare” appunto i primi args numeri — per chi non avesse conoscenze di programmazione args è passato come argomento da linea di comando — assumendo da principio che tutti i numeri siano primi, ed eliminando man mano tutti quelli che hanno divisori, o meglio eliminando i multipli dei primi trovati fino a quel punto.

Una versione più moderna e sicuramente più efficace del crivello di Eratostene è il crivello di Atkins, un test di primalità che può essere trovato oltre che su Wikipedia, anche su altri siti. Inoltre rimando alle interessanti letture (e codici) di The Prime Pages, che faranno la gioia di qualsiasi programmatore/matematico che ancora non si sia interessato alla questione.