Implementazioni di algoritmi/Crivello di Eratostene

Wikibooks, manuali e libri di testo liberi.
Indice del libro


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.

Implementazione in C[modifica]

#include <stdio.h>
#include <stdlib.h>

#ifdef INT128BIT
	//Con questa definizione l'algoritmo dovrebbe supportare interi a 128bit.
	//Richiede la compilazione con GCC e processore a 64bit per SO UNIX. Purtroppo
	//non è stato testato e non può essere considerato funzionante.	
	#include <stdint.h>
	typedef uint64_t __int_t;
	//Definizione del numero massimo del setaccio.
	//Ricordate che se dichiarate n, il valore massimo controllato sarà n-1!
	//il valore definito è il massimo possibile per questo tipo
	#define UPPER_LIMIT UINT64_MAX 
#endif


#ifndef INT128BIT
	typedef unsigned long int __int_t;
	//Definizione del numero massimo del setaccio.
	//Ricordate che se dichiarate n, il valore massimo controllato sarà n-1!
	//il valore definito è il massimo possibile per questo tipo.
	#define UPPER_LIMIT 65534
#endif

#define MAXNUM 5000

int main()
{
	//Definizione variabili
	__int_t* num_matrix;
	__int_t i=0, t=0, k=2;
	int a=0; //(solo per la stampa dei risultati)

	if ( MAXNUM >= UPPER_LIMIT )
		return 1;
	
	//Inizializza il vettore del setaccio.
	num_matrix=(__int_t*)malloc(MAXNUM*sizeof(__int_t));
	
	for (i=0; i < MAXNUM; i++)
		num_matrix[i]=i;
			
	//Eliminazione dal crivello di 1
	num_matrix[1]=0;
	
	//Crivello di Eratostene.
	//Si consideri che l'algoritmo è semplificato e potrebbe essere
	//enormemente migliorato, evitando ad esempio cicli inutili.
	//Pseudocodice:
	//per i da 0 al valore massimo
	//	per il multiplo k di i
	//		per t da 0 al valore massimo
	//			se il numero t del vettore non è già stato eliminato
	//				se il resto della divisione intera tra il numero t \
	//				e il multiplo k di i è uguale da zero
	//					escludi il numero t dal vettore (=0)
	for (i = 0; i < MAXNUM; i++)
	{
		if ( num_matrix[i] != 0 )
		{
			for (k = 2; k < MAXNUM; k++)
			{
				for (t = 0; t < MAXNUM; t++)
				{
					if ( num_matrix[t] != 0 )
					{
						if ( (num_matrix[t]%(k*i)) == 0 )
							num_matrix[t]=0;
					};
				};
			};
		};
	};
	//Fine algoritmo
		
	//Stampa risultati (10 per riga)
	i=0; a=0;
	for (i=i; i < MAXNUM; i++)
	{
		if ( num_matrix[i] != 0 )
		{	
			fprintf(stdout, "%ld\t", num_matrix[i]);
			a++;
			if ( a == 9 ) 
			{
				fprintf(stdout, "\n");
				a=0;
			};
		};
	};
	
	free(num_matrix);
	system("pause");
}

Implementazione in PHP[modifica]

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";
        }
}

Implementazione in Python[modifica]

def crivello(ma):
  """Restituisce la lista dei numeri primi minori o uguali a ma.

     Crea una lista con i numeri compresi 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


Implementazione in Python[modifica]

def Crivello(n):
    num = list(range(n+1))
    num[1] = 0
    for x in range(int(n**0.5)+1):
            if num[x] != 0:
                    num[2*x::x] = [0]*(int(n/x)-1)
    return list(filter(None, num))