Scusate se intervengo molto in ritardo, ma propongo un paio di algoritmi
che, hanno tempi paragonabili a quelli migliori, ma risultano molto più
semplici.
Questo cerca di ottimizzare l'algoritmo:
def crivello7(n):
if n <= 2:
return []
c = list(range(3, n, 2))
top=len(c)
for primo in c:
if primo:
base = (primo*primo - 3) // 2
if base >= top:
break
for j in range(base, top, primo):
c[j]=0
return [2] + list(filter(None, c))
Questo usa le capacità di Python:
def sieveOfEratostenes2(n):
if n <= 2:
return []
sieve = list(range(3, n, 2))
top = len(sieve)
for si in sieve:
if si:
bottom = (si*si - 3) // 2
if bottom >= top:
break
sieve[bottom::si] = [None] * -((bottom - top) // si)
return [2] + list(filter(None, sieve))
Come il precedente ma usa numpy:
def sieveOfEratostenes3(n):
if n <= 2:
return []
sieve = numpy.arange(3, n, 2, dtype = int)
top = len(sieve)
for si in sieve:
if si:
bottom = (si*si - 3) // 2
if bottom >= top:
break
sieve[bottom::si] = 0
return [2] + list(filter(None, sieve))
Sono algoritmi suggeriti, se non sbaglio da Bearophile
Ciao
--
Daniele
www.fugamatematica.blogspot.com
giusto!
nel verso
forse è perché non guardiamo le cose
Quando non ci capiamo,
_______________________________________________
Python mailing list
Python@lists.python.it
http://lists.python.it/mailman/listinfo/python
