Crivello di Eratostene
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.
Algoritmo
#!/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
/* 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;
}
Altro metodo
#include <stdio.h>
#include <conio.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++)
/*fracca cula*/
/*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();
getch();
return 0;
}
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";
}
}
Voci correlate
Una evoluzione del crivello di Eratostene è rappresentata dal crivello di Atkin, un algoritmo creato circa nel 1999.