[Python] crivello Atkin?

[Pietro Battiston]

Il giorno lun, 15/03/2010 alle 23.59 +0100, Nicola Ferrari ha scritto:
> Ciao a tutti..
> stavo "giocando" con ProjectEuler.
> Il problema 10
> (http://projecteuler.net/index.php?section=problems&id=10) mi sta
> dando un po' di problemi..
> i tempi di risoluzione superano i 2 minuti, e io volevo rispettare le
> specifiche del sito, che prevedono che i tempi di risoluzione
> inferiori al minuto..
> 
> Ho provato a riutilizzate il generatore infinito di numeri primi
> (http://stacktrace.it/2008/01/progetto-eulero-problema-3/) ma i tempi
> restano cmq alti..
> 
> Qualcuno sa illustrarmi qualche metodo per velocizzare il tutto?
> Ho letto su wikipedia che c'è il crivello di Atkin che migliora le
> prestazioni di quello di Eratostene... 
> Qualcuno ferrato in materia può spiegarmi Atkin o darmi delle
> documentazioni che lo spiegano?
> 
> La spiegazione fornita da wikipedia non la capisco..

Neanch'io, ma forse c'è qualcos'altro che non capisco: i seguenti
comandi

>>> l = [True] * 2000000
>>> for i in range(2, 2000):
...     if l[i]:
...         for j in range(2, 2000000/i):
...             l[i*j] = False
>>> print sum([i for i in range(2, 2000000) if l[i]])


richiedono meno di 10 secondi sul mio computer. C'è qualcosa che mi
sfugge?

ciao

Pietro