Implementazioni di algoritmi/Crivello di Eratostene: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Annullata la modifica 332608 di 138.41.3.14 (discussione) |
|||
Riga 2:
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 [[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}}
| |||