Implementazioni di algoritmi/Crivello di Eratostene

Wikibooks, manuali e libri di testo liberi.

Sommario
Categoria · Copertina · Sviluppo · modifica il template

Copertina Implementazioni di algoritmi/Copertina


Il crivello di Eratostene è un antico procedimento per il calcolo delle tabelle di numeri primi fino ad un certo numero n prefissato. Deve il nome al matematico Eratostene di Cirene, che ne fu l'ideatore. È a tutt'oggi utilizzato come algoritmo di calcolo dei numeri primi da molti programmi per computer; pur non essendo un algoritmo straordinariamente efficiente, infatti, è in compenso piuttosto semplice da tradurre in un qualsiasi linguaggio di programmazione.

[modifica] Implementazione in C

#include <stdio.h>
#define LENGTH 2500
 
int main(int argc, char *argv[]) {
    unsigned long int numb[LENGTH];
    unsigned long int i=0, k=2;
 
    for( i=0; i<LENGTH; i++ ) {
        numb[i] = i;
    }
    numb[1] = 0;
    i = 0 ;
    while( i<LENGTH ) {     
        if( numb[i] == 0 ) {
            i++; 
        } else {
            for( k=2; (k*i) <= LENGTH; k++ ) {
                numb[k*i] = 0;
            }
            i++; 
        }
    }
 
    for( i=0; i<LENGTH; i++ ) {
        if( numb[i]!=0 ) {
            printf("%d\n", numb[i] ); 
        }
    }
}

[modifica] Implementazione in PHP

function crivella($size=1000){
        //Dichiaro le variabili
        $a=$b=0;
 
        //Riempio il vettore da 0 a 1000 con il valore 1
        $numeri=array_fill(0, $size, 1);
 
        //Scorro i numeri dal 2 fino a $size
        for($a=2;$a<$size;$a++){
                //Se il vettore nella posizione [$a] è uguale ad 1
                if($numeri[$a]==1){
                        //eseguo un ciclo da [$a+$a] fino a $size
                        for($b=$a+$a;$b<$size;$b+=$a)
                                //e azzero ogni elemento multiplo di a
                                $numeri[$b]=0;
                }
        }
 
        //Output dei numeri primi che hanno nel vettore il valore 1
        for($a=2;$a<$size;$a++){
                if($numeri[$a]==1)
                        echo "$a\n";
        }
}

[modifica] Implementazione in Python

def crivello(ma):
  """Restituisce la lista dei numeri primi minori o uguali a ma.
 
     Crea una lista con i numeri comresi tra 2 e ma+1,
     esegue l'algoritmo del crivello di Eratostene:
     lascia il primo e toglie tutti i suoi multipli,
     passa al secondo e procede così fino NON alla fine,
     ma a quando il nuovo numero primo
     non supera la radice di ma+1."""
  c=range(3, ma+1, 2)
  i=0
  while c[i]<(ma+1)**0.5:
    j=i+1
    while j<len(c):
      if c[j] % c[i] == 0: del c[j]
      j+=1
    i+=1
  return [2]+c

Ricavato da "http://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Crivello_di_Eratostene"
Strumenti personali