Crivello di Eratostene
Da Wikipedia, l'enciclopedia libera.
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.
Il procedimento è il seguente: si scrivono tutti i naturali a partire da 2 fino n in un elenco detto setaccio (in programmazione spesso l'elenco è implementato da un array). Poi si cancellano (setacciano) tutti i multipli del primo numero del setaccio (escluso lui stesso). Si prosegue così fino ad arrivare in fondo. I numeri che restano sono i numeri primi minori od uguali a n. È come se si utilizzassero dei setacci a maglie via via più larghe: il primo lascia passare solo i multipli di 2, il secondo solo i multipli di 3, e così via.
Nel caso n = 50, ad esempio, il procedimento di setacciatura si conclude con il numero 7 perché 7 è il massimo intero il cui quadrato non supera 50 e si può provare che il procedimento di setacciatura per ricercare i primi fino ad un certo numero n cessa sempre quando si supera la radice quadrata di n. Infatti ogni numero a del setaccio iniziale, contenente tutti i numeri naturali non superiori ad un dato n, cade dal setaccio che corrisponde al più piccolo dei suoi divisori primi.
Se indichiamo con p il più piccolo divisore primo di a si ha: 
con 
.
Se ne deduce che 
da cui p è sempre minore o uguale alla radice quadrata di a.
Indice |
[modifica] Algoritmo
[modifica] Implementazione in Bashscript
#!/bin/bash # sieve.sh # Crivello di Eratostene # di Stephane Chazelas # Si deve invocare con un argomento da linea di comando. LIMITE_SUPERIORE=$1 # Da linea di comando. let META=sqrt(LIMITE_SUPERIORE) # Metà del numero massimo. Primi=( '' $(seq $LIMITE_SUPERIORE) ) i=1 until (( ( i += 1 ) > META )) # È sufficiente verificare solo la metà dei numeri. do if [[ -n $Primi[i] ]] then t=$i until (( ( t += i ) > LIMITE_SUPERIORE )) do Primi[t]= done fi done echo ${Primi[*]} exit 0
[modifica] Implementazione in C
/* Copyright Emanuele Piccolini - Codice sotto GNU/GPLv2 - Si deve invocare con un argomento da linea di comando. */ #include <stdio.h> #include <stdlib.h> #include <math.h> void Eratostene(int *array,int upperbound); int main(int argc, char **argv) { int upperbound,i; int *array=NULL; if(argc<2) return 0; /* Copia Upperbound */ upperbound = atoi(argv[1]); if(upperbound > 0){ /* Allocazione e Popolamento dell'Array */ array = (int *) malloc(upperbound * sizeof(int) ); for(i=0;i<upperbound;i++) array[i] = (i+1); /* Crivello di Eratostene */ Eratostene(array,upperbound); /* Stampa degli elementi rimasti, ovvero i primi */ for(i=0;i<upperbound;i++) if(array[i] != -1) printf("%d ",array[i]); printf("\n"); /* Distruzione dell'Array */ free(array); array = NULL; } return 0; } void Eratostene(int *array,int upperbound){ int pi,i; /* Creazione Array Perno */ int * perni = malloc(((int)sqrt(upperbound))*sizeof(int)); /* Popolamento array perno */ for(i=0;i<((int)sqrt(upperbound));i++) perni[i] = (i+1); /* Cancellazione Multipli dei perni */ for(pi=1;pi<((int)sqrt(upperbound));pi++){ for(i=0;i<upperbound;i++) if(((array[i]%perni[pi])==0) && (array[i] != perni[pi])) array[i] = -1; } free(perni); return; }
[modifica] Altro Metodo in C
Altro metodo
#include <stdio.h> #define SIZE 1000 int main() { /*Dichiaro il vettore di SIZE dimensione */ int numeri[SIZE]; int a,b; /*Inizializzo ad 1 ogni elemento*/ for(a=0;a<SIZE;a++) numeri[a]=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; /*Outputo i numeri primi che hanno nel vettore il valore 1*/ for(a=2;a<SIZE;a++) if(numeri[a]==1) printf("%d \n",a); getchar(); return 0; }
[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 Visual basic 6.0
Public Sub NumeriPrimi_Temino89() Dim vett(1 To 10000) As Boolean, Dividendo as Integer, Divisore as Integer Dim Resto as Integer For I = 2 To 10000 Dividendo = I If vett(Dividendo) = False Then For Z = 2 To 10000 Divisore = Z If Dividendo <> Divisore And Divisore > Dividendo Then Resto = Divisore Mod Dividendo If vett(Z) = False Then If Resto = False Then vett(Z) = True Else vett(Z) = False End If End If End If Next Z End If Next I End Sub
[modifica] Voci correlate
Una evoluzione del crivello di Eratostene è rappresentata dal crivello di Atkin, un algoritmo creato circa nel 1999.
