Wikibooks

Implementazioni di algoritmi/Crivello di Eratostene: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
m Annullate le modifiche di 138.41.3.14 (discussione), riportata alla versione precedente di 95.225.49.18
Pagina svuotata
Etichetta: blanking
Riga 1:
{{Implementazioni di algoritmi}}
 
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]]===
<source lang="c">
#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");
}
</source>
 
===Implementazione in [[PHP]]===
<source lang="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";
}
}
</source>
===Implementazione in [[Python]]===
<source lang="python">
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
</source>
[[Categoria:Implementazioni di algoritmi|Crivello di Eratostene]]
{{Avanzamento|100%|29 luglio 2008}}
Estratto da "https://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Crivello_di_Eratostene"