Re: [Python] crivello Atkin?
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=problemsid=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] * 200 for i in range(2, 2000): ... if l[i]: ... for j in range(2, 200/i): ... l[i*j] = False print sum([i for i in range(2, 200) if l[i]]) richiedono meno di 10 secondi sul mio computer. C'è qualcosa che mi sfugge? ciao Pietro ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] crivello Atkin?
2010/3/16 Pietro Battiston too...@email.it La spiegazione fornita da wikipedia non la capisco.. Neanch'io, ma forse c'è qualcos'altro che non capisco: i seguenti comandi l = [True] * 200 for i in range(2, 2000): ... if l[i]: ... for j in range(2, 200/i): ... l[i*j] = False print sum([i for i in range(2, 200) if l[i]]) richiedono meno di 10 secondi sul mio computer. C'è qualcosa che mi sfugge? Direi nulla tranne qualche condizione al contorno... :-) Ciao. Marco. -- http://python.thinkcode.tv - Videocorso di Python http://stacktrace.it - Aperiodico di resistenza informatica http://beri.it - Blog di una testina di vitello ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] crivello Atkin?
Il giorno mar, 16/03/2010 alle 10.19 +0100, Marco Beri ha scritto: 2010/3/16 Pietro Battiston too...@email.it La spiegazione fornita da wikipedia non la capisco.. Neanch'io, ma forse c'è qualcos'altro che non capisco: i seguenti comandi l = [True] * 200 for i in range(2, 2000): ... if l[i]: ... for j in range(2, 200/i): ... l[i*j] = False print sum([i for i in range(2, 200) if l[i]]) richiedono meno di 10 secondi sul mio computer. C'è qualcosa che mi sfugge? Direi nulla tranne qualche condizione al contorno... :-) Se intendi il -1, mi stupirebbe che quello richiedesse 10 minuti :-) Pietro ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] crivello Atkin?
2010/3/16 Pietro Battiston too...@email.it Direi nulla tranne qualche condizione al contorno... :-) Se intendi il -1, mi stupirebbe che quello richiedesse 10 minuti :-) Ah, ah! :-)) Si, intendevo il +1 da aggiungere a un paio di for e il +2000 da aggiungere alla prima inizializzazione per evitare index error. Comunque se anche questo problema non richiede un generatore di numeri primi molto veloce, ti garantisco che nei problemi più avanti questo diventa indispensabile ;-) Ciao. Marco. -- http://python.thinkcode.tv - Videocorso di Python http://stacktrace.it - Aperiodico di resistenza informatica http://beri.it - Blog di una testina di vitello ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] crivello Atkin?
Il giorno mar, 16/03/2010 alle 10.39 +0100, Marco Beri ha scritto: 2010/3/16 Pietro Battiston too...@email.it Direi nulla tranne qualche condizione al contorno... :-) Se intendi il -1, mi stupirebbe che quello richiedesse 10 minuti :-) Ah, ah! :-)) Si, intendevo il +1 da aggiungere a un paio di for e il +2000 da aggiungere alla prima inizializzazione per evitare index error. già! Comunque se anche questo problema non richiede un generatore di numeri primi molto veloce, ti garantisco che nei problemi più avanti questo diventa indispensabile ;-) Allora sarà il caso che resisto alla tentazione di leggerli! ciao Pietro ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] crivello Atkin?
2010/3/16 Pietro Battiston too...@email.it Allora sarà il caso che resisto alla tentazione di leggerli! Sì, te lo consiglio. Io sono rimasto intrippato nella scimmia del 100% e oramai non riesco più a starne fuori... :-( Ciao. Marco. -- http://python.thinkcode.tv - Videocorso di Python http://stacktrace.it - Aperiodico di resistenza informatica http://beri.it - Blog di una testina di vitello ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] crivello Atkin?
Marco..Non scoraggiarmi.. :) Il giorno 16 marzo 2010 14.19, Marco Beri marcob...@gmail.com ha scritto: 2010/3/16 Pietro Battiston too...@email.it Allora sarà il caso che resisto alla tentazione di leggerli! Sì, te lo consiglio. Io sono rimasto intrippato nella scimmia del 100% e oramai non riesco più a starne fuori... :-( Ciao. Marco. -- http://python.thinkcode.tv - Videocorso di Python http://stacktrace.it - Aperiodico di resistenza informatica http://beri.it - Blog di una testina di vitello ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python -- Nicola Ferrari website: http://www.nicolaferrari.name skype: nick.ferro ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] crivello Atkin?
2010/3/16 Nicola Ferrari nick.fe...@gmail.com Marco..Non scoraggiarmi.. :) Assolutamente! Figurati! Al limite ti metto in guardia... ;-) -- http://python.thinkcode.tv - Videocorso di Python http://stacktrace.it - Aperiodico di resistenza informatica http://beri.it - Blog di una testina di vitello ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
